18. 四数之和

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

解法一：

和15. 3Sum 差不多，3sum用了三个游标i，front，back。这里用四个：i，j，front，back。j从i+1开始到末尾，其他的同3sum的做法，用front和back夹逼即可 代码注意在i的while循环中夹着j的while循环

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        nums.sort()
        i = 0
        while i < len(nums):
            j = i+1
            while j < len(nums):                
                front, back = j+1, len(nums)-1               
                while front < back:
                    tmp_sum = nums[i] + nums[j] + nums[front] + nums[back]
                    if tmp_sum < target:
                        front += 1
                    elif tmp_sum > target:
                        back -= 1
                    else:
                        #四元组
                        quad = [nums[i], nums[j], nums[front], nums[back]]
                        res.append(quad)
                        while front < back and nums[front] == quad[2]:
                            front += 1
                        while front < back and nums[back] == quad[3]:
                            back -= 1
                while j+1 < len(nums) and nums[j+1] == nums[j]:
                    j += 1
                j += 1    #结束j循环
            while i+1 < len(nums) and nums[i+1] == nums[i]:
                i += 1
            i += 1    #结束i循环
        return res