【LeetCode】0018 四数之和

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

# -*- coding:utf-8 -*-

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        # 选定a
        for i in range(len(nums)):
            # 选定b
            if i > 0 and nums[i] == nums[i- 1]:
                continue
            new_target = target - nums[i]
            new_nums = nums[i + 1:]
            for j in range(len(new_nums) - 2):
                left = j + 1
                right = len(new_nums) - 1
                if j > 0 and new_nums[j] == new_nums[j - 1]:
                    continue
                while left < right:
                    temp = new_nums[j] + new_nums[left] + new_nums[right]
                    if temp == new_target:
                        res_list = [nums[i], new_nums[j], new_nums[left], new_nums[right]]
                        res_list.sort()
                        res.append(res_list)
                        left += 1
                        right -= 1
                        # 初步去重（相当于剪枝？）
                        while left < right and new_nums[left] == new_nums[left - 1]:
                            left += 1
                        while left < right and new_nums[right] == new_nums[right + 1]:
                            right -= 1
                    if temp > new_target:
                        right -= 1
                    if temp < new_target:
                        left += 1
        return res
if __name__ == '__main__':
    nums = [-3, -2, -1, 0, 0, 1, 2, 3]
    target = 0
    print(Solution().fourSum(nums, target))

思路：这道题和之前三数之和大相径庭，只不过可以把a+b+c+d=target变成b+c+d=target-a即可。同时由于需要循环a和b的值，所以在每次循环之前都要判断当前索引的ab值和上一次的一不一样（if i > 0 and nums[i] == nums[i- 1]）。

思考：同时在评论中注意到了一个非常有意思的剪枝操作，就是用最大和最小可能出现的值作为剪枝，如当选定索引0为a时，计算0、1、2、3这四个数的和——也就是abcd和的理论最小值，如果不在结果范围则直接跳过、同理处理最大值。可以节约非常多的时间。