给定一个包含 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] ]通过次数112,058 提交次数290,816 代码实现
无优化代码 class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() if len(nums)<4: return [] res = [] for i in range(len(nums)-3): for j in range(len(nums)-1, i+2, -1): cur = nums[i]+nums[j] k = i+1 while i<k<j: red = target-cur-nums[k] if red<nums[k]: break if red not in nums[k+1:j]: k+=1 continue if [nums[i],nums[j],nums[k],red] not in res: res.append([nums[i],nums[j],nums[k],red]) k+=1 return res 优化代码 class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() hashs = {} for i in range(len(nums)): for j in range(i+1,len(nums)): temp = nums[i]+nums[j] if temp not in hashs: hashs[temp] = [[i,j]] else: hashs[temp].append([i,j]) res = [] pref1 = None if len(nums) <4: return res for f1 in range(len(nums)-3): if nums[f1]==pref1: continue pref1 = nums[f1] pref2 = None for f2 in range(f1+1, len(nums)-2): if nums[f2]==pref2: continue pref2 = nums[f2] target2 = target-pref1-pref2 if target2 not in hashs: continue temps = hashs[target2] pref3 = None for i in temps: if i[0]<=f2 or nums[i[0]]==pref3: continue pref3 = nums[i[0]] res.append([pref1,pref2,nums[i[0]],nums[i[1]]]) return res 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。