18. 四数之和

难度中等997

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

我的解析思路：

有了前面的两数之和的基础，我首先想到的利用双指针的方法来解决这个问题；整个调试过程真的很艰难，最后在自己的努力下终于AC了（虽然时空复杂度并不是很优秀）。

调试过程主要要注意一下几点：

• 双指针的前提要先排序
• 题目要求同一个位置的元素相同的话就视为重复的四元组，所以在处理第一个元素和第二个元素的时候我分别利用f1和f2标记重复元素的个数，如果是相同元素的时候就结束本次循环，直到不是重复元素为止。这里需要注意的是：f2为了避免最外层的上一次的循环的标记给下一次的结果造成错误的影响，所以每次循环之前要对它设置为0，否则就会出错。
• 对于每次的第三个元素（left）重复的处理要注意：一直移动到倒数第二个重复的值的位置，因为可能存在第四个元素（right）为这个重复值的情况。还要判断它有没有使用，如果没有使用，而是继续自己使用的情况，那就是重复四元组。
• 同样的要处理第四个元素。
• 对于找到目标值之后而不是跳出循环，而是继续移动第三个元素。因为可能存在中间的两个值相加等于外层两个数相加的情况，所以不能漏掉。

我的代码：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        result_ls = []
        len_nums = len(nums)
        #线排序一下，这样就可使用双指针的方法
        nums.sort()
        #print(nums)
        f1 = 0
        f2 = 0
        for element1 in range(len_nums - 3):
            if f1 > 0:
                f1 -= 1
                continue
            f2 = 0
            for element2 in range(element1 + 1, len_nums - 2):
                left = element2 + 1
                right = len_nums - 1
                if f2 > 0:
                    f2 -= 1
                    continue
                while(left < right):

                    sum = nums[element1] + nums[element2] + nums[left] + nums[right]
                    #print(element1, element2, left, right)
                    if sum == target:
                        #print('resut',element1, element2, left, right)
                        t_ls = []
                        t_ls.append(nums[element1])
                        t_ls.append(nums[element2])
                        t_ls.append(nums[left])
                        t_ls.append(nums[right])
                        result_ls.append(t_ls)
                        left += 1
                        while left < right and nums[left] == nums[left - 1]:
                            #print('left', left)
                            left += 1
                        # 特殊情况就是留给right的一个值他并没有使用，而是继续自己使用的情况，那就是重复值
                        sum_new = nums[element1] + nums[element2] + nums[left] + nums[right]
                        if left + 1 == right and nums[left] == nums[left + 1] and (sum == target or sum_new > target):
                            break
                    elif sum < target:
                        left += 1
                        #print('-2',left,right)
                        while left + 1 < right and nums[left] == nums[left - 1]:
                            #print('left', left)
                            left += 1
                        # 特殊情况就是留给right的一个值他并没有使用，而是继续自己使用的情况，那就是重复值
                        sum_new = nums[element1] + nums[element2] + nums[left] + nums[right]
                        if left + 1 == right and nums[left] == nums[left + 1] and (sum == target or sum_new > target):
                            break
                    else:
                        right -= 1
                        #print('-1',left,right)
                        while left < right - 1 and nums[right] == nums[right + 1]:
                            #print('  ri -1')
                            right -= 1
                        sum_new = nums[element1] + nums[element2] + nums[left] + nums[right]
                        # 同样的，特殊情况就是留给left的一个值他并没有使用，而是继续自己使用的情况，那就是重复值
                        if left == right - 1 and nums[right] == nums[right - 1] and (sum == target or sum_new < target):
                            #print('le == ri -1')
                            break
                while element2 < left and nums[element2] == nums[element2 + 1]:
                    #print('ele2', element2)
                    element2 += 1
                    f2 += 1
            while element1 < len_nums - 3 and nums[element1] == nums[element1 + 1]:
                #print('ele1', element1)
                element1 += 1
                f1 += 1
        return result_ls

 运行结果：

参考答案：

分析：

四数之和，和15.三数之和是一个思路，都是使用双指针法, 基本解法就是在15.三数之和 的基础上再套一层for循环。

但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。（大家亲自写代码就能感受出来）

15.三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下表作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下表作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。

那么一样的道理，五数之和、六数之和等等都采用这种解法。

对于15.三数之和双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。

之前我们讲过哈希表的经典题目：454.四数相加II，相对于本题简单很多，因为本题是要求在一个集合中找出四个数相加等于target，同时四元组不能重复。

而454.四数相加II是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于本题还是简单了不少！

我们来回顾一下，几道题目使用了双指针法。

双指针法将时间复杂度O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：

• 27.移除元素
• 15.三数之和
• 18.四数之和

操作链表：

• 206.反转链表
• 19.删除链表的倒数第N个节点
• 面试题 02.07. 链表相交
• 142题.环形链表II

双指针法在字符串题目中还有很多应用，后面还会介绍到。

 参考代码：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]: continue
            for k in range(i+1, n):
                if k > i + 1 and nums[k] == nums[k-1]: continue
                p = k + 1
                q = n - 1

                while p < q:
                    if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
                    elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
                    else:
                        res.append([nums[i], nums[k], nums[p], nums[q]])
                        while p < q and nums[p] == nums[p + 1]: p += 1
                        while p < q and nums[q] == nums[q - 1]: q -= 1
                        p += 1
                        q -= 1
        return res

运行结果：