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

2021-05-31 364 words 2 minutes

Contents

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” 我們峰頂見!!!