ericpuwang

四数之和

https://leetcode.cn/problems/4sum/

给你一个由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
• 10^9 <= nums[i] <= 10^9
• 10^9 <= target <= 10^9

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans = []
        for index, num in enumerate(nums[:-3]):
            # num已经计算过,避免重复计算
            if index and num == nums[index-1]:
                continue
            # 由于数组升序,故index后续任意四个数组之和都大于target
            if num + nums[index+1] + nums[index+2] + nums[index+3] > target:
                break
            # 可能存在四数之和等于target
            if num + nums[-1] + nums[-2] + nums[-3] < target:
                continue
            for index2, num2 in enumerate(nums[index+1:-2]):
                # 计算正确的索引
                index2 = index2 + index + 1
                # 跳过已经计算过的重复数字
                if index2 > index + 1 and num2 == nums[index2-1]:
                    continue
                if num + num2 + nums[index2+1] + nums[index2+2] > target:
                    break
                if num + num2 + nums[-1] + nums[-2] < target:
                    continue

                j = index2 + 1
                k = len(nums) - 1
                while j < k:
                    s = num + num2 + nums[j] + nums[k]
                    if s < target:
                        j += 1
                    elif s > target:
                        k -= 1
                    else:
                        ans.append([num, num2, nums[j], nums[k]])
                        j += 1
                        while j < k and nums[j] == nums[j-1]:
                            j += 1
                        k -= 1
                        while j < k and nums[k] == nums[k+1]:
                            k -= 1
        return ans