18. 四数之和

说明

给定一个包含 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] ]

题解思路

在三数之和的基础上多一层循环

代码实现

class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() n = len(nums) ans = [] for a in range(n-3): if a > 0 and nums[a] == nums[a - 1]: continue for b in range(a+1, n-2): if b > a + 1 and nums[b] == nums[b-1]: continue d = n - 1 tar = target - nums[a] - nums[b] for c in range(b+1, n-1): # print(a,b,c,d) if c > b + 1 and nums[c] == nums[c-1]: continue while c < d and nums[c] + nums[d] > tar: d -= 1 if c == d: break if nums[c] + nums[d] == tar: ans.append([nums[a], nums[b], nums[c], nums[d]]) return ans