18. 四数之和-medium.md

Description

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution

1. 次优解

• 对数组进行排序，便于区分冗余项
• 先定位第一个元素，之后转化为 15. 三数之和 问题使用双指针求解
• 存在优化空间：使用哈希表将时间复杂度优化至 $O(n^3)$

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []

        for i in range(len(nums)-3):
            if i != 0 and nums[i-1] == nums[i]:
                continue
            for j in range(i+1, len(nums)-2):
                if j != i+1 and nums[j-1] == nums[j]:
                    continue
                start, end = j+1, len(nums)-1
                tmp_target = target - nums[i] - nums[j]
                while end > start:
                    if nums[start] + nums[end] > tmp_target:
                        end -= 1
                    elif nums[start] + nums[end] < tmp_target:
                        start += 1
                    else:
                        res.append([nums[i], nums[j], nums[start], nums[end]])
                        start += 1
                        end -= 1
                        while start < end and nums[start-1] == nums[start]:
                            start += 1
                        while start < end and nums[end+1] == nums[end]:
                            end -= 1
        return res

2.最优解（from 题解）

• TODO：理解题解优化方法

 from collections import Counter
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        dic = Counter(nums) #对每个数出现的次数进行统计
        arr = sorted(dic.keys())  #排序键值
        for i, a in enumerate(arr):
            dic[a] -= 1 #a用掉了一次，而且a的位置之后不会再遍历到了，不需要加回
            for j, b in enumerate(arr[i:]):  #从arr[i]开始找b的值
                if dic[b] < 1: #b可能等于a，判断一下，如果dic[b]不够1个，跳过这次循环
                    continue
                dic[b] -= 1
                for c in arr[i+j:]:  #从arr[i+j]开始找c的值，注意上一层循环枚举j以后，需要再加最外层的i
                    if dic[c] < 1: #同上层循环b的判断
                        continue
                    d = target - (a + b + c)  
                    if d < c:   #因为是非递减顺序，如果d小于c，就直接跳出，这样就可以避免重复
                        break
                    if (d == c and dic[d] > 1) or (d > c and dic[d] > 0):
                        res.append([a, b, c, d])
                dic[b] += 1 #b现在所处的位置，之后a还会遍历到，因此需要加回1
        return res