Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.

Example 1:

 12345678 Given array nums = [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] ] 

Related Topics: ArrayTwo PointersHash Table

## 解題邏輯與實作

### Two Pointers

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() length = len(nums) answers = [] for head_idx, head in enumerate(nums[:-3]): if head_idx > 0 and head == nums[head_idx-1]: continue self.threeSum(nums[head_idx+1:], target-head, head, answers) return answers def threeSum(self, nums: List[int], target: int, head: int, answers:List[List[int]]) -> List[List[int]]: if not nums: return [] length = len(nums) for first_idx, first in enumerate(nums[:-2]): if first_idx > 0 and first == nums[first_idx-1]: continue diff = target - first second_idx = first_idx + 1 third_idx = length -1 while(second_idx < third_idx): second = nums[second_idx] third = nums[third_idx] summation = second + third if summation < diff: second_idx += 1 elif summation > diff: third_idx -= 1 else: answers.append([head, first,second,third]) while(second_idx < third_idx and nums[second_idx] == nums[second_idx+1]): second_idx += 1 while(second_idx < third_idx and nums[third_idx] == nums[third_idx-1]): third_idx -= 1 second_idx += 1 third_idx -= 1 return answers