Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.

Example 1:

Given array nums = [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]
]

Related Topics: Array、Two Pointers、Hash Table

解題邏輯與實作

Two Pointers

我這題一開始直接偷懶使用 3Sum 來回作答。

class Solution:
   def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
      nums.sort()
      length = len(nums)
      answers = []
      for head_idx, head in enumerate(nums[:-3]):
         if head_idx > 0 and head == nums[head_idx-1]:
            continue
                        
         self.threeSum(nums[head_idx+1:], target-head, head, answers)                  
      return answers
            
   def threeSum(self, nums: List[int], target: int, head: int, answers:List[List[int]]) -> List[List[int]]:
      if not nums:
         return []

      length = len(nums) 

      for first_idx, first in enumerate(nums[:-2]):
         if first_idx > 0 and first == nums[first_idx-1]:
            continue


         diff = target - first
         second_idx = first_idx + 1
         third_idx = length -1	

         while(second_idx < third_idx): 
            second =   nums[second_idx] 
            third = nums[third_idx]
                              
            summation = second + third   

            if summation < diff:
                second_idx += 1
            elif summation > diff:
                third_idx -= 1
            else:				
                answers.append([head, first,second,third]) 
                while(second_idx < third_idx and nums[second_idx] == nums[second_idx+1]):
                   second_idx += 1

                while(second_idx < third_idx and nums[third_idx] == nums[third_idx-1]):
                   third_idx -= 1

                second_idx += 1
                third_idx -= 1

      return answers

結果比我想像中好一點，我原本預期會超時，不過也沒好到哪裡去就是了只跑出了 804 / 47.58%。

上面這個勉強算是 Two Pointers ，但這題的 Tag 中還有一個 Hash Table 解法，先欠著吧，我好想睡 Orz

其他連結

1. 【LeetCode】0000. 解題目錄

本文作者： 辛西亞．Cynthia
本文連結： 辛西亞的技能樹 / hackmd 版本
版權聲明： 部落格中所有文章，均採用 姓名標示-非商業性-相同方式分享 4.0 國際 (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！