18.四数之和
https://leetcode-cn.com/problems/4sum/
难度：中等
题目：
给定一个包含n 个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c和 d，
使得a + b + c + d的值与target相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
提示：
- 0 <= nums.length <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
示例：
示例 1： 输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 示例 2： 输入：nums = [], target = 0 输出：[]
分析
如果之前做过 两数之和 ,
三数之和 ,
那么，这道题就是无脑多嵌套一层for循环了...
双层for循环判断num1和num2，然后使用双指针执行while循环，直到left == right截止。
解题：
class Solution: def fourSum(self, nums, target): nums.sort() ln = len(nums) ret = [] if ln < 4: return [] for i in range(0, ln - 3): num1 = nums[i] for j in range(i + 1, ln - 2): num2 = nums[j] left = j + 1 right = ln - 1 while left < right: total = num1 + num2 + nums[left] + nums[right] if total == target: tmp = [num1, num2, nums[left], nums[right]] if tmp not in ret: ret.append(tmp) right -= 1 elif total < target: left += 1 else: right -= 1 return ret
