1.题目

原题：

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

2.解析

这道题的本质是k数相加的问题，之前有类似的两数相加和三数相加问题，这道问题上升为四数相加，如果用暴力求解法，时间复杂度会很高。考虑之前题目的特点，实际上所有的k数相加问题都可以用双指针两端逼近降低算法的复杂度。
先更新一下自己的思路：首先将数组由小到大排列；其次设置双指针，判断数值大小移动指针位置。前两层是循环控制初始的1，2位置，第三个是移动指针m，第四个是移动指针k(数组长度减1)。存在以下情况

• 如果四数和大于target，则k-1;
• 如果四数之和小于target，则m+1；
• 如果四数之和等于target，则需要根据情况判断，一般做法是m+1的同时k-1以实现全部的判断。这里笔者进行了优化就是根据剩余数字和当前移动指针对应值得大小情况跟新m和k，如果游标和小于剩余值之和，说明要想再达到相等应该优先从较大值开始更新，反之则从较小值更新。

3.python代码

class Solution:
    def fourSum(self, nums, target):
        nums.sort()
        print(nums)
        l = len(nums)
        nums_set = []
        for i in range(l):
            for j in range(i+1, l):
                m = j + 1
                k = l - 1
                while m < k:
                    print(i, j, m, k)
                    tmp = nums[i] + nums[j] + nums[m] + nums[k]
                    if tmp == target:
                        nums_set.append([nums[i], nums[j], nums[m], nums[k]])
                        if nums[k] + nums[m] <= sum(nums[m+1:k]):
                            k -= 1
                        else:
                            m += 1
                    elif tmp > target:
                        k -= 1
                    else:
                        m += 1
        # nums_set = [list(a) for a in set([tuple(num) for num in nums_set])]
        return nums_set

附录

做题过程中有一些知识点和错误的地方值得思考，所以把它记录下来。

• 知识点1，list方法append和extend的用法，extend方法是将一个列表加到另外一个列表后边，最后形成的是一个列表。append方法我们最常用的是单元素插入列表中，其实这个方法也可以将一个list插入到另一个list中，形成一个二维的列表。
• 知识点2，while循环中的break和continue，continue是不执行以下的代码进入下一次迭代，break是直接跳出循环。
  -知识点3，列表去重，set具有去重的作用，但是没法直接对二维列表使用，将二维列表转化为tuple以后就可以使用set进行去重，最后再转回list即可。
  其实，这次的思路是采用双层循环，同样采用双指针进行两端逼近，问题在于对于满足四数之和等于target的处理，如果直接跳出会错过很多其他可能的情况，如果进行判断则会增加时间复杂度，但是也可以测试通过（别忘记注释掉调试过程中的print）。