【LeetCode】0018. 4Sum

| | |

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:

1
2
3
4
5
6
7
8
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 來回作答。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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. 解題目錄