给定一个包含 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] ]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
在 3 sum 上多了一层循环,关于 3 sum,请参考:http://timd.cn/leetcode/k-sum/three-sum/
class Solution(object): def fourSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[List[int]] """ nums.sort() ret = [] for i in range(len(nums) - 3): if i > 0 and nums[i] == nums[i - 1]: continue for t in self.threeSum(nums, i + 1, target-nums[i]): ret.append([nums[i]] + t) return ret def threeSum(self, nums, start, target): ret = [] for p1 in range(start, len(nums) - 2): if p1 > start and nums[p1] == nums[p1 - 1]: continue left = p1 + 1 right = len(nums) - 1 while left < right: a = nums[p1] + nums[left] + nums[right] - target if a == 0: ret.append([nums[p1], nums[left], nums[right]]) while left < right and nums[left + 1] == nums[left]: left = left + 1 left = left + 1 while right > left and nums[right - 1] == nums[right]: right = right - 1 right = right - 1 elif a < 0: left = left + 1 else: right = right - 1 return ret