题目描述如下
给定一个包含 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]
]
解题思路为找到所有不重复的满足a+b+c+d=target的四个数,为了做到不重复,首先可以用排序的方式来避免重复
可以将原数组按照非递减的顺序进行排序,再顺序查找a,b,c,d,哈希表可以加速查询的速度,同时也是可以统计每个数出现的次数。
以数组nums = [1, 0, -1, 0, -2, 2]为例,则
In [1]:
nums = [1, 0, -1, 0, -2, 2]
In [4]:
from collections import Counter
In [2]:
res=[]
In [5]:
dic = Counter(nums)
In [6]:
dic
Out[6]:
In [7]:
arr = sorted(dic.keys())
In [8]:
arr
Out[8]:
接着是嵌套便利,最外层遍历到什么地方,就将对应的数的个数-1,然后在内层循环里也把选择的数的数量-1,如果这个数已经没了,那么就用continue跳过。
四数之和和三数之和的差别在于,第二个数选择的时候要 -1,最内层循环结束以后还要 +1,因为之后最外层的 a 也会再遍历到这个位置。
总代码如下
from collections import Counter
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
dic = Counter(nums) #对每个数出现的次数进行统计
arr = sorted(dic.keys()) #排序键值
for i, a in enumerate(arr):
dic[a] -= 1 #a用掉了一次,而且a的位置之后不会再遍历到了,不需要加回
for j, b in enumerate(arr[i:]): #从arr[i]开始找b的值
if dic[b] < 1: #b可能等于a,判断一下,如果dic[b]不够1个,跳过这次循环
continue
dic[b] -= 1
for c in arr[i+j:]: #从arr[i+j]开始找c的值,注意上一层循环枚举j以后,需要再加最外层的i
if dic[c] < 1: #同上层循环b的判断
continue
d = target - (a + b + c)
if d < c: #因为是非递减顺序,如果d小于c,就直接跳出,这样就可以避免重复
break
if (d == c and dic[d] > 1) or (d > c and dic[d] > 0):
res.append([a, b, c, d])
dic[b] += 1 #b现在所处的位置,之后a还会遍历到,因此需要加回1
return res