Chen's Blog

18. 4Sum

 
  • 2023年 06月11日

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

  1. if nums is empty: return []
  2. sort the nums, we need the list is sorted.
  3. def result:list to store the final result
  4. def the find two sum pairs to find the c, d.
    1. need var: nums, left, right, target
    2. def pairs:list to store the c and d
    3. while left<right
      1. if nums[left]+nums[right]<target: left +=1
      2. if nums[left]+nums[right]>target: right -= 1
      3. if nums[left]+nums[right] == target:
        1. if pairs not exist or pairs[-1] != (nums[i], nums[j]) # judge if overlap
        2. add (nums[left], nums[right]) to pairs
        3. left += 1, right -= 1
      4. return pairs

      📓need to move the left and right index. the left is j+1, and right always is len(nums)-1.

  5. i is a and j is b, fix a and b
    1. loop i in len(nums)
    2. loop j in (i+1, len(nums))
    3. find c, d
      1. pairs = self.find_two_sum_pairs(nums, j+1, len(nums), target-nums[i]-nums[j])
    4. 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

  1. sort the nums
  2. def res to store the final result.
  3. def length is the len(nums)
  4. loop i is a in (0, length-3) # because dont need care the final 3 number.
  5. de-duplicated, if i and nums[i] == nums[i-1]: continue
  6. loop j is b in (i+1, length-2) # because dont need care the final 2 number.
  7. de-duplicated, if j != i+1 and nums[i] == nums[j-1]: continue;
  8. def sum = target - nums[i] - nums[j]
  9. def left, right = j+1, length - 1
  10. while left < right:
    1. if nums[left] + nums[right] == sum:
      1. res.append([nums[i], nums[j], nums[left], nums[right]])
      2. right -= 1
      3. left += 1
      4. while left < right and nums[left] == nums[left-1]:left += 1 # de-duplicated
      5. while left < right and nums[right] == nums[right+1]: right -= 1 # de-duplicated
    2. if nums[left] + nums[right] > sum: right -= 1
    3. if nums[left] + nums[right] < sum: left += 1
  11. 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
搜索