哈希表——5.四数之和

力扣题目链接

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

示例：

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

其实题目的思路与上一章三数之和一脉相承，只不过多加了一层for循环

那么在代码部分应该进行哪些修改呢，完整代码如下：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        result = []
        for i in range(n):
            if nums[i] > target and nums[i] > 0 and target > 0:# 剪枝（可省）
                break
            if i > 0 and nums[i] == nums[i-1]:# 去重
                continue
            for j in range(i+1, n):
                if nums[i] + nums[j] > target and target > 0: #剪枝（可省）
                    break
                if j > i+1 and nums[j] == nums[j-1]: # 去重
                    continue
                left, right = j+1, n-1
                while left < right:
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if s == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif s < target:
                        left += 1
                    else:
                        right -= 1
        return result

        nums.sort()
        n = len(nums)
        result = []

首先，同样先对数组进行排序，计算数组长度，定义一个放置结果的控数组。

        for i in range(n):
            if nums[i] > target and nums[i] > 0 and target > 0:# 剪枝（可省）
                break
            if i > 0 and nums[i] == nums[i-1]:# 去重
                continue

进入第一层循环，即四元组的第一个数。先进行剪枝，减少时间。当第一个数大于目标数且该数和目标数都大于0则之间退出循环。那为什么要设置第一个数和目标数都大于0的前置条件呢，是因为如果例如第一个数为-4，第二个数为-3，目标数为-7时。第一个数-4大于-7，如果只根据nums[i] > target那么就退出循环了，但是第二个数是-3，两数加起来就等于目标数了，那么这种情况就会被忽略，导致最后结果数组中缺失该种情况的组合。（但个人感觉代码中nums[i] > 0可以不用添加）

接着就很简单了，把它当做一个for循环下的三数之和做就行。

            for j in range(i+1, n):
                if nums[i] + nums[j] > target and target > 0: #剪枝（可省）
                    break
                if j > i+1 and nums[j] == nums[j-1]: # 去重
                    continue

当前两个数之和大于目标数且目标数大于0，那么就结束循环。接着，面对第一层循环中的i（即四元组第一个数）和第二层循环中的j（即四元组中第二个数），对于j和j之后连续的数如果与j的数值一样，则不断将j向后移动。

                left, right = j+1, n-1
                while left < right:
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if s == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif s < target:
                        left += 1
                    else:
                        right -= 1

设置左右指针，接下来就和三数之和的代码编写思路一样了，我就不做赘述了，可以去看我对三数之和代码的分析。

其实这两道题目，你理解了之后就不难，最主要是在代码编写时的逻辑不要乱，以及重复值情况要考虑完整。