【LeetCode】（No.018） 四数之和
NO.18 四数之和
一、写在前面
刷题模块的初衷是恶补数据结构和算法，不管自己的公众号怎样变化，刷题这个模块一定会保留下去，期待自己能成为offer收割机。LeetCode 第十七题传输门：【LeetCode】（No.017）电话号码的字母组合今天给大家分享的是LeetCode 第十八题：四数之和。
前十题汇总：【LeetCode】打卡记录（NO.1-10）为面试而生，期待你的加入。
二、今日题目
给定一个包含 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]
]三、 分析
四数之和真的来了，之前做过两数之和【打卡贴】（No.001）从零开始刷LeetCode，两数相加【打卡贴】（No.002）从零开始刷LeetCode，三数之和【LeetCode】（No.015）三数之和，最接近的三数之和【LeetCode】（No.016）最接近的三数之和 这个题和之前的三数之和解题思路是差不多的，这次用了两种方法字典查找法和四指针夹逼法。
字典查找使用两个循环，第一个for循环，先求后2个值可能的取值的所有情况，并且把它们储存在一个字典里，以和作为键。第二个for循环，我们遍历前2个值所可能取的各种值，算出和并且检查target - onesum是否在字典里，如果在，就说明我们找到了一个解。其实这种求几数之和的问题，都可以通过这种思路。
四指针夹逼定义i,j,point_left,point_right四个指针。因为经过了排序，i到point_right递增。如果i也就是第一个指针的四倍大于等于target, break。如果最大一项的三倍小于还需要填充的和，则进入下个更大的i。同理它这里的if保证了不重复计算相同的i。
简单来说用字典查找法，先遍历求出后几个值的可能取值，并用字典去存储，最后去搜索target - nums[i]-nums[j]。用夹逼法，声明4个指针，后2个指针用来夹逼。
四、解题
第一种解题：
1class Solution:
2 def fourSum(self, nums, target):
3 """
4 :type nums: List[int]
5 :type target: int
6 :rtype: List[List[int]]
7 """
8 nums.sort()
9 ans = set()
10 sumans = {}
11 if len(nums) < 4:
12 return []
13 for i in range(2, len(nums) - 1):
14 for j in range(i+1, len(nums)):
15 onesum = nums[i] + nums[j]
16 if onesum not in sumans:
17 sumans[onesum] = [(i, j)]
18 else:
19 sumans[onesum].append((i, j))
20 for i in range(len(nums) - 3):
21 for j in range(i+1, len(nums) - 2):
22 onesum = nums[i] + nums[j]
23 if target - onesum in sumans:
24 for k in sumans[target - onesum]:
25 if k[0] > j:
26 ans.add((nums[i], nums[j], nums[k[0]], nums[k[1]]))
27 return [i for i in ans]
28
29}
第二种解题：
1 class Solution:
2 def fourSum(self, nums, target):
3 """
4 :type nums: List[int]
5 :type target: int
6 :rtype: List[List[int]]
7 """
8
9
10 if not nums:
11 return []
12
13 _4_sum_list = []
14 nums.sort()
15 if nums[-1]*4 < target:
16 return []
17 for i in range(len(nums)-3):
18 if nums[i]*4 > target:
19 break
20 if i==0 or nums[i]!= nums[i-1]:
21 ele = nums[i]
22 target_3_sum = target - ele
23 if nums[-1]*3 < target_3_sum:
24 continue
25 for j in range(i+1,len(nums)-2):
26 ele2 = nums[j]
27 if ele2*3 > target_3_sum:
28 break
29 if j==i+1 or ele2!= nums[j-1]:
30 target_2_sum = target_3_sum - ele2
31 point_left = j+1
32 point_right = len(nums)-1
33 while point_left < point_right:
34 if nums[point_left] + nums[point_right] > target_2_sum:
35 point_right -= 1
36 elif nums[point_left] + nums[point_right] < target_2_sum:
37 point_left += 1
38 else:
39 aaa = [ele, ele2,nums[point_left], nums[point_right]]
40 _4_sum_list.append(aaa)
41 point_left += 1
42 point_right -= 1
43 while point_left < point_right and nums[point_left] == nums[point_left-1]:
44 point_left += 1
45 while point_left < point_right and nums[point_right] == nums[point_right+1]:
46 point_right -= 1
47
48
49 return _4_sum_list
50
51
52}