Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 15. 3Sum

發表於 分類於 ， ， Disqus：
這題是一個運用指標的算法，而且是用三個指標來追蹤

前言

　　這題是一個運用指標的算法，而且是用三個指標來追蹤，運用指標依序掃瞄出題目所要的元素並加起來，使用到了 for、while 兩個迴圈，時間複雜度估達 O(n²)，這裡有 JAVA 和 Python 的寫法。

題目

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.

給定一個整數陣列 nums，回傳所有的三元組，其中 i != j, i != k, j != k，且三元組全部加起來等於 0。
注意 這個解決方案必須不含重複的三元組。

題目連結：https://leetcode.com/problems/3sum/

題目限制

3 <= nums.length <= 3000
105 <= nums[i] <= 105

範例

1
2
3
4
5
6
7
8
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
1
2
3
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
1
2
3
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

思路&筆記

直觀的作法是設定三個指標來掃描，第一個指標先不動，另外兩個指標依序掃描元素，掃描後把全部的元素加起來，判斷裡面的合有沒有等於 0 的，有的話就加入在要輸出的陣列裡，資料結構想到的是把陣列裡的元素個別放進集合裡，再將每一組串列集合放進 HashSet 大集合裡，HashSet 好處是可過濾掉重複的組合。

  • 將 Array 從小到大排序
  • 找出三個數的指標分別表示為 i、j、k
  • 使用迴圈遍歷，並將 i 做為 nums 的起始點 (指標一)
  • j 則為 i + 1 為起始 (指標二)
  • k 則為 nums.Length - 1 為起始點 (指標三)
  • 首先以 i 為準，從 j 開始掃描到 k 算一輪
  • 並判斷三個指標指向的元素 nums[i] + nums[j] + nums[k] 加起來的合是否為 0 ，是的話會把此組合加進串列集合內
  • 之後讓 j 前進一格，K 後退一格，來排除重複的組合找到下一個組合
  • 由於元素從小排到大，當 sum < target 的話，表示說我們的 j 要繼續往右掃描到一個更大的元素，加起來的合再做判斷
  • 那元素從小排到大，當 sum > target 的話，表示說我們的 k 要繼續往左掃描到一個更小的元素，加起來的合再做判斷

[備註] 使用 HashSet 是為了確保集合裡的資料不重複

簡易示意圖

1
2
3
4
5
6
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|  i  |  j  |     |     |     |  k  |

sum = (-4) + (-1) + 2 = -3
sum < 0，j++
1
2
3
4
5
6
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|  i  |     |  j  |     |     |  k  |

sum = (-4) + (-1) + 2 = -3
sum < 0，j++
1
2
3
4
5
6
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|  i  |     |     |  j  |     |  k  |

sum = (-4) + 0 + 2 = -2
sum < 0，j++
1
2
3
4
5
6
7
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|  i  |     |     |     |  j  |  k  |

sum = (-4) + 1 + 2 = -1
sum < 0，j++
j == k，回到最新一輪，i++
1
2
3
4
5
6
7
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|     |  i  |  j  |     |     |  k  |

sum = (-1) + (-1) + 2 = 0，加進集合
j++
k--
1
2
3
4
5
6
7
8
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|     |  i  |     |  j  |  k  |     |

sum = (-1) + 0 + 1 = 0，加進集合
j++
k--
j > k，回到最新一輪，i++
1
2
3
4
5
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|     |     |  i  |  j  |     |  k  |

i 與上次相同，回到最新一輪，i++
1
2
3
4
5
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|     |     |     |  i  |  j  |  k  |

sum = 0 + 1 + 2 = 3

JAVA 實現

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        int target = 0; // 目標整數
        Arrays.sort(nums); // 從小到大排序 (原Array)
        Set<List<Integer>> s = new HashSet<>(); // 存元素
        List<List<Integer>> output = new ArrayList<>(); // 輸出用

        for (int i = 0; i < nums.length; i++){
            int j = i + 1; // 指標二
            int k = nums.length - 1; // 指標三
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k]; // 指標全加起來
                if (sum == target) {
                    // 將陣列元素轉成集合再加到大集合內
                    s.add(Arrays.asList(nums[i], nums[j], nums[k])); // 類似這樣的資料結構 [[1, 2, 3], [2, 3, 4]]
                    // 縮小範圍
                    j++; 
                    k--;
                } else if (sum < target) {
                    j++; // 找更大的元素
                } else {
                    k--; // 找更小的元素
                }
            }
        }
        output.addAll(s); // 集合加到陣列裡
        return output;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        target = 0 # 目標整數
        nums.sort() # 從小到大排序 (原Array)
        s = set() # 存元素的集合
        output = [] # 輸出用的陣列
        
        for i in range(len(nums)):
            j = i + 1 # 指標二
            k = len(nums) - 1 # 指標三
            while j < k:
                total = nums[i] + nums[j] + nums[k] # 指標全加起來
                if total == target:
                    s.add((nums[i], nums[j], nums[k])) # 將陣列元素加到集合內
                    # 縮小範圍
                    j = j+1 
                    k = k-1
                elif total < target:
                    j = j+1 # 找更大的元素
                else:
                    k = k-1 # 找更小的元素
        
        output.extend(list(s)) # 添加進陣列
        return output

成績

Language Runtime Memory
Java 706ms 50.8MB
Python 2857ms 20.2MB