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
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
