0 Comments

[LeetCode][python3]0018. 4Sum

Start the journey
N2I -2020.04.02

1. My first try

  1. class Solution:
  2.  def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
  3.   ans=[]
  4.   nums=sorted(nums)
  5.   for a,tar_a in enumerate(nums[:-3]):
  6.    b=a+1
  7.    for tar_b in nums[a+1:-2]:
  8.     c=b+1
  9.     d=len(nums)-1
  10.     while d>c:
  11.      #print(a,b,c,d)
  12.      tar_c=nums[c]
  13.      tar_d=nums[d]
  14.      if tar_a+tar_b+tar_c+tar_d==target:
  15.       if [tar_a,tar_b,tar_c,tar_d] not in ans:
  16.        ans.append([tar_a,tar_b,tar_c,tar_d])
  17.       else:
  18.        c+=1
  19.        d-=1
  20.      elif tar_a+tar_b+tar_c+tar_d>target:
  21.       d-=1
  22.      else:
  23.       c+=1
  24.     b+=1
  25.   return ans

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

  1. class Solution:
  2.     def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
  3.         if not nums:
  4.             return []
  5.         nums = sorted(nums)
  6.         res = []
  7.         self.kSum(nums, 0, len(nums)-1, 4, target, [], res)
  8.         return res
  9.         
  10.     
  11.     def kSum(self, nums, left, right, k, target, state, res):
  12.         # not enough
  13.         if k < 2 or right - left + 1 < k:
  14.             return
  15.         if k * nums[left] > target or k * nums[right] < target:
  16.             return 
  17.         if k == 2:
  18.             # reduce to 2 sum problem
  19.             while left < right:
  20.                 cur = nums[left] + nums[right]
  21.                 if cur == target:
  22.                     res.append(state + [nums[left], nums[right]])
  23.                     left += 1
  24.                     while left < right and nums[left] == nums[left - 1]:
  25.                         left += 1
  26.                 elif cur > target:
  27.                     right -= 1
  28.                 else:
  29.                     left += 1
  30.         else:
  31.             # k > 2, reduce the degree
  32.             for i in range(left, right+1):
  33.                 if i == left or i > left and nums[i] != nums[i-1]:
  34.                     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

  1. class Solution:
  2.     def fourSum(self, nums, target):
  3.         if not nums: 
  4.             return []
  5.         nums=sorted(nums)
  6.         numsLen = len(nums)
  7.         dic = {j:i for i, j in enumerate(nums)}
  8.         ans = set()
  9.         N = nums[-1]
  10.         for idx, num1 in enumerate(nums[:-3]):
  11.             if num1 + 3 * N < target: 
  12.                 continue
  13.             if 4 * num1 > target: 
  14.                 break
  15.             for j in range(idx + 1, numsLen - 2):
  16.                 num2 = nums[j]
  17.                 if num1 + num2 + 2 * N < target: 
  18.                     continue
  19.                 if num1 + 3 * num2 > target: 
  20.                     break
  21.                 for k in range(j + 1, numsLen - 1):
  22.                     c = nums[k]
  23.                     temp = target - num1 - num2 - c
  24.                     if temp > N: 
  25.                         continue
  26.                     if temp < c: 
  27.                         break
  28.                     if temp in dic and dic[temp] > k: 
  29.                         ans.add((num1, num2, c, temp))
  30.         return ans

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.