Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
思路其实非常简单,无非是把4Sum问题转化为3Sum问题。
class Solution: def fourSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[List[int]] """ # 特殊情况,数字个数小于4 n = len(nums) if n < 4: return [] nums = sorted(nums) i = 0 results = [] while i < n-3: self.threesum(nums[i+1:], target-nums[i], nums[i], results) i += 1 # repeat situation while (i<n-3) and (nums[i] == nums[i-1]): i += 1 return results def threesum(self, nums, target, first, results): i = 0 n = len(nums) while i < n-2: left = i + 1 right = n-1 while left < right: val = nums[i] + nums[left] + nums[right] if val == target: results.append([first, nums[i], nums[left], nums[right]]) print([first, nums[i], nums[left], nums[right]]) left += 1 right -= 1 # repeat situation while (left< right) and (nums[left]==nums[left-1]): left += 1 while (left<right) and (nums[right]==nums[right+1]): right -= 1 elif val < target: left += 1 else: right -= 1 i += 1 # repeat situation while (i < n -2) and nums[i] == nums[i-1]: i += 1 return None
近期评论