Contents

[Golang][Leetcode][Array]刷題系列-15-Two Pointers


15. 3Sum


Level : Medium

原題連結 : Click

題目 :

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.


Example :

Note

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]


解題思路 :

  • 這個題目需要考慮的事情:
    1. 他不能有重複的組合出現
    2. 他回傳的是value本身不是index

  • 根據以上原因,使用two pointers的解法較為方便,他有點像第11題的Container的問題,就是不斷縮小範圍
  • 所以我們需要先將nums array先做排序(小到大)
  • 接下來,由於不能有重複所以我們設定base, low, high,sum = base + high + low,讓所有元素除了最後兩個都當一輪base
  • 那 high 跟 low 呢? high從最大的數字也就是最右邊開始,low則是從base的下一個(假設base是0,low就是 0 + 1 = 1)
  • 只要sum大於0 => 那代表我們需要將high變小,所以 high–
  • 只要sum小於0 => 那代表我們需要將low變大,所以 low++
  • 不斷的縮小範圍直到閉合,就換下一個base,然後凡事用過的base就不會再出現了
  • 這裡有三個判斷需要注意:
    1. 如果nums array小於三個都就直接結束程式
    2. 如果該base與他上一個base是同一個數字可以直接跳過這個base,因為他所有的組合已經包含在上一輪base裡面了
    3. 既然有連續的base的filter,也需要加上連續high,low的filter

以下是我的解法 - time complexity:O(n^2) , space complexity: O(1)

Runtime: 28 ms, faster than 93.88% of Go online submissions for 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import "sort"

func threeSum(nums []int) [][]int {
    
    var res [][]int
    
    length := len(nums)
    
    if length < 3 {
        return res
    }
    
    sort.Ints(nums)
    
    var low, high, sum int
    
    target := 0
    
    for i := 0; i < length-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        
        low = i+1
        high = length-1
        
        for low < high {
            
            sum = nums[i] + nums[low] + nums[high]
            
            
            if sum == target && high > low {
                res = append(res, []int{nums[i], nums[low], nums[high]})
                high--
                for nums[high] == nums[high+1] && high > low {
                    high--
                }
                
                low++
                
                for nums[low] == nums[low-1] && high > low {
                    low++
                }
            }            
            if sum > target && high > low {
                
                high--
                // for nums[high] == nums[high+1] && high > low {
                //     high--
                // }
            }
            
            if sum < target && high > low {
                low++
                // for nums[low] == nums[low-1] && high > low {
                //     low++
                // }           
            }
            
        }
          
    }
    
    return res
    
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life我們峰頂見!!!