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] ]
In [16]:
import pdb
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
# nums list length
nums_len = len(nums)
# sorted nums list
nums.sort()
ans = []
# pdb.set_trace()
for i in range(nums_len - 3):
# remove duplicated i
if i and nums[i] == nums[i-1]:
continue
target_i = target - nums[i]
for j in range(i+1, nums_len - 2):
if j > (i + 1) and nums[j] == nums[j-1]:
continue
target_ij = target_i - nums[j]
left, right = j + 1, nums_len - 1
while left < right:
tmp = target_ij - nums[left] - nums[right]
if tmp == 0:
ans.append([nums[i], nums[j], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left +=1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif tmp > 0:
left += 1
else:
right -= 1
return ans
In [17]:
Solution().fourSum([1, 0, -1, 0, -2, 2], 0) # answer is [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Out[17]:
In [18]:
Solution().fourSum([0, 0, 0, 0], 0) # answer is [[0, 0, 0, 0]] remove duplicate j while add j > (i+1)
Out[18]:
In [ ]: