Ruka
3 min readApr 2, 2020

[LeetCode][python3]0018. 4Sum

Start the journey
N2I -2020.04.02

  1. My first try
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
ans=[]
nums=sorted(nums)
for a,tar_a in enumerate(nums[:-3]):
b=a+1
for tar_b in nums[a+1:-2]:
c=b+1
d=len(nums)-1
while d>c:
#print(a,b,c,d)
tar_c=nums[c]
tar_d=nums[d]
if tar_a+tar_b+tar_c+tar_d==target:
if [tar_a,tar_b,tar_c,tar_d] not in ans:
ans.append([tar_a,tar_b,tar_c,tar_d])
else:
c+=1
d-=1
elif tar_a+tar_b+tar_c+tar_d>target:
d-=1
else:
c+=1
b+=1
return ans
N2I -2020.04.02

Explanation:

This is a classic way to solve 4 sum problems. It is better than an O(n³) solution but still cost too much time.

2. A Recursive Solution

class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if not nums:
return []
nums = sorted(nums)
res = []
self.kSum(nums, 0, len(nums)-1, 4, target, [], res)
return res


def kSum(self, nums, left, right, k, target, state, res):
# not enough
if k < 2 or right - left + 1 < k:
return
if k * nums[left] > target or k * nums[right] < target:
return
if k == 2:
# reduce to 2 sum problem
while left < right:
cur = nums[left] + nums[right]
if cur == target:
res.append(state + [nums[left], nums[right]])
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
elif cur > target:
right -= 1
else:
left += 1
else:
# k > 2, reduce the degree
for i in range(left, right+1):
if i == left or i > left and nums[i] != nums[i-1]:
self.kSum(nums, i+1, right, k-1, target-nums[i], state+[nums[i]], res)
N2I -2020.04.02

Explanation:

The solution is a classic recursive way to solve this kind of problems. It reduce its degree in every recursion. Puts any situation into a 2 Sum problem.

3. A better solution

class Solution:
def fourSum(self, nums, target):
if not nums:
return []
nums=sorted(nums)
numsLen = len(nums)
dic = {j:i for i, j in enumerate(nums)}
ans = set()
N = nums[-1]
for idx, num1 in enumerate(nums[:-3]):
if num1 + 3 * N < target:
continue
if 4 * num1 > target:
break
for j in range(idx + 1, numsLen - 2):
num2 = nums[j]
if num1 + num2 + 2 * N < target:
continue
if num1 + 3 * num2 > target:
break
for k in range(j + 1, numsLen - 1):
c = nums[k]
temp = target - num1 - num2 - c
if temp > N:
continue
if temp < c:
break
if temp in dic and dic[temp] > k:
ans.add((num1, num2, c, temp))
return ans
N2I -2020.04.02

Explanation:

The main idea in the solution is to limit the searching fragment and low down the time cost. The two if condition num1+num2+2*N<target and num1+3*num2>target are the keys. They are both conditions with results no answers in all kind of situations. The dic saves the last index of every duplicate numbers. The solution use this to check if answer is unique.

Ruka
Ruka

Written by Ruka

HI I’m Ruka. Now a SWE in Taiwan. Contact via email: nayzi9999@gmail.com

No responses yet