题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：

  1. [
  2.   [-1,  0, 0, 1],
  3.   [-2, -1, 1, 2],
  4.   [-2,  0, 0, 2]
  5. ]

方案一

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if len(nums) < 4:
            return []
        # 使用三数之和同样的方式，不过本次使用四个指针
        nums.sort()

        res = set()
        a, b = 0, 1
        while a < len(nums) - 3:
            b = a + 1
            while b < len(nums) - 2:
                i = b + 1
                j = len(nums) - 1
                while i < j:
                    count = nums[a] + nums[b] + nums[i] + nums[j]
                    if count == target:
                        res.add((nums[a], nums[b], nums[i], nums[j]))
                        i += 1
                        j -= 1
                    elif count < target:
                        i += 1
                    else:
                        j -= 1

                b += 1
            a += 1

        return [list(item) for item in res]
  • 注意点一，固定的指针为最前面的两个指针；移动完毕内部指针后，固定的内部指针交替移动；
  • 注意点二，移动指针时可以跳过值相同的元素来降低时间复杂度；
  • 注意点三，每次循环中发现和大于目标值，则移动指针使其和增大；反之相反。

    leetcode性能最高的方案

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

        m = len(nums)
        if m < 4:
            return []

        res = []

        nums = sorted(nums)
        i = 0
        while(i < m-3):
            if (i > 0 and nums[i] == nums[i-1]):
                i += 1
                continue
            if (nums[i]+nums[i+1]+nums[i+2]+nums[i+3]) > target:
                i += 1
                break
            if (nums[i]+nums[-3]+nums[-2]+nums[-1]) < target:
                i += 1
                continue
            j = i+1
            while(j < m-2):
                if (j > i+1 and nums[j] == nums[j-1]):
                    j += 1
                    continue
                if (nums[i] + nums[j]+ nums[j+1] + nums[j+2]) > target:
                    j += 1
                    break
                if (nums[i] + nums[j]+ nums[-2] + nums[-1]) < target:
                    j += 1
                    continue
                left = j + 1
                right = m -1
                sumtemp = target - nums[i] - nums[j]
                while(left < right):
                    temp = nums[left] + nums[right]
                    if temp < sumtemp:
                        left += 1
                    elif temp > sumtemp:
                        right -= 1
                    else:
                        combination = []
                        combination.append(nums[i])
                        combination.append(nums[j])
                        combination.append(nums[left])
                        combination.append(nums[right])
                        res.append(combination)
                        left += 1
                        while(left < right and nums[left] == nums[left-1]):
                            left -= 1
                        right -= 1
                        while(left < right and nums[right] == nums[right+1]):
                            right -= 1
                j += 1
            i += 1

        return res