Promble
link: https://leetcode.com/problems/4sum/
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- 0 <= a, b, c, d < n
- a, b, c, and d are distinct.
- nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Approach 1
fix a, b find c, d.
Thought
- if nums is empty: return []
- sort the nums, we need the list is sorted.
- def result:list to store the final result
- def the find two sum pairs to find the c, d.
- need var: nums, left, right, target
- def pairs:list to store the c and d
- while left<right
- if nums[left]+nums[right]<target: left +=1
- if nums[left]+nums[right]>target: right -= 1
- if nums[left]+nums[right] == target:
- if pairs not exist or pairs[-1] != (nums[i], nums[j]) # judge if overlap
- add (nums[left], nums[right]) to pairs
- left += 1, right -= 1
- return pairs
📓need to move the left and right index. the left is j+1, and right always is len(nums)-1.
- i is a and j is b, fix a and b
- loop i in len(nums)
- loop j in (i+1, len(nums))
- find c, d
- pairs = self.find_two_sum_pairs(nums, j+1, len(nums), target-nums[i]-nums[j])
- prepare the final result
Code
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if not nums:
return []
nums = sorted(nums)
results = []
# i is a and j is b, fix a and b
for i in range(len(nums)):
# dont compare the same num
if i>0 and nums[i] == nums[i-1]:
continue;
for j in range(i+1, len(nums)):
# dont compare the same num
if j>i+1 and nums[j] == nums[j-1]:
continue;
# find c, d
pairs = self.find_two_sum_pairs(
nums,
j+1, # left
len(nums) - 1, # right
target - nums[i] - nums[j], # target
)
# combintaion the c, d with a, b
for (c, d) in pairs:
results.append([nums[i], nums[j], c, d])
return results
def find_two_sum_pairs(self, nums, left, right, target):
# target is the sum of c and d number, store to pairs list.
pairs = []
while left<right:
if nums[left] + nums[right] < target:
left += 1
elif nums[left] + nums[right] > target:
right -= 1
else: # when target = nums[left]+nums[right]
if not pairs or (nums[left], nums[right]) != pairs[-1]:
pairs.append((nums[left], nums[right]))
left += 1
right -= 1
return pairs
Complexity
时间复杂度
- loop i $O(n)$, loop j $O(n)$, find two sum paris $O(n)$.
- prepare result $O(n)$.
- 总时间复杂度: $O(n^3)$
Approach 2
the other method for fix two point and find the other two point. need to de-duplicated.
Thought
- sort the nums
- def res to store the final result.
- def length is the len(nums)
- loop i is a in (0, length-3) # because dont need care the final 3 number.
- de-duplicated, if i and nums[i] == nums[i-1]: continue
- loop j is b in (i+1, length-2) # because dont need care the final 2 number.
- de-duplicated, if j != i+1 and nums[i] == nums[j-1]: continue;
- def sum = target - nums[i] - nums[j]
- def left, right = j+1, length - 1
- while left < right:
- if nums[left] + nums[right] == sum:
- res.append([nums[i], nums[j], nums[left], nums[right]])
- right -= 1
- left += 1
- while left < right and nums[left] == nums[left-1]:left += 1 # de-duplicated
- while left < right and nums[right] == nums[right+1]: right -= 1 # de-duplicated
- if nums[left] + nums[right] > sum: right -= 1
- if nums[left] + nums[right] < sum: left += 1
- if nums[left] + nums[right] == sum:
- return res
📓left only can +1, right only can -1
Code
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
res = []
length = len(nums)
# first a, so - 3
for i in range(0, length-3):
if i and nums[i] == nums[i-1]:
continue;
# second b, so - 2
for j in range(i+1, length -2):
if j != i+1 and nums[j] == nums[j-1]:
continue;
sum = target - nums[i] - nums[j]
left, right = j+1, length-1
# find c, d
while left < right:
if nums[left] + nums[right] == sum:
res.append([nums[i], nums[j], nums[left], nums[right]])
right -= 1
left += 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
elif nums[left] + nums[right] > sum:
right -= 1
else:
left += 1
return res