18. 四数之和

一、题目描述

给定一个包含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]
]

二、思路

1. 双指针

参考LeetCode中腐烂的橘子的题解

• 因为结果中不能包含重复的四元组，所以可以先对数组进行递增排序，方便后边去重。

• 采用三层循环，依次创建四个指针i、j、k、m

• 三层循环会大幅增加时间开销，所以可以在循环中进行条件判断，避免无用循环。

  • 比如最外层循环内可以加上判断条件：nums[i] + 3 * nums[i+1] > target，因为nums为递增排序，所以再往后运算的数值也必定大于target，所以此处可以直接break。
  • 接下来对条件nums[i] + 3 * num[-1] < target判断，此时nums[i]加上任意其他的三个数也一定小于target，所以此处可以直接进行下次循环了。
    • 此处下一个数进行判断，如果nums[i] == nums[i+1]，执行i += 1，以此来达到去重的效果。

三、代码实现

1. 双指针

class Solution:
    def fourSum(self, nums, target):
        length = len(nums)
        nums.sort()
        result = []

        i = 0
        while i < length -3:    # 第一层循环，选择第一个数，后边还有三个数，所以要减去3
            if nums[i] + 3 * nums[i+1] > target: 
                break
            if nums[i] + 3 * nums[-1] < target:
                while i < length-4 and nums[i] == nums[i+1]:    # 去重
                    i += 1
                i += 1    # 此处指针指向的数与下一个数不相同，但是与前一个数还是相同的，所以要加1
                continue
            diff1 = target - nums[i]

            j = i + 1
            while j < length - 2:
                if nums[j] + 2 * nums[j+1] > diff1: 
                    break
                if nums[j] + 2 * nums[-1] < diff1:
                    while j < length - 3 and nums[j] == nums[j+1]:
                        j += 1
                    j += 1
                    continue
                diff2 = diff1 - nums[j]

                k = j + 1
                m = length - 1     # 同时对后两个数判断
                while k < m:
                    if nums[k] + nums[m] < diff2: 
                        k += 1
                    elif nums[k] + nums[m] > diff2: 
                        m -= 1
                    else:
                        result.append([nums[i], nums[j], nums[k], nums[m]])
                        k += 1
                        m -= 1

                        while nums[k] == nums[k-1] and k < m:     # 去重
                            k += 1
                        while nums[m] == nums[m+1] and k < m: 
                            m -= 1

                while j < length - 3 and nums[j] == nums[j+1]:
                    j += 1
                j += 1

            while i < length - 4 and nums[i] == nums[i+1]:
                i += 1
            i += 1
        return result

四、表现

执行用时	表现	内存消耗	表现
88ms	91.96%	13.5MB	12.78%