這題是一個運用指標的算法,而且是用三個指標來追蹤,運用指標依序掃瞄出題目所要的元素並加起來,使用到了 for、while 兩個迴圈,時間複雜度估達 O(n²)
,這裡有 JAVA 和 Python 的寫法。
Given an integer array nums, return all the triplets
[nums[i], nums[j], nums[k]]
such thati != j
,i != k
, andj != k
, andnums[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
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.
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
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
是為了確保集合裡的資料不重複
| -4 | -1 | -1 | 0 | 1 | 2 |
|-----|-----|-----|-----|-----|-----|
| i | j | | | | k |
sum = (-4) + (-1) + 2 = -3
sum < 0,j++
| -4 | -1 | -1 | 0 | 1 | 2 |
|-----|-----|-----|-----|-----|-----|
| i | | j | | | k |
sum = (-4) + (-1) + 2 = -3
sum < 0,j++
| -4 | -1 | -1 | 0 | 1 | 2 |
|-----|-----|-----|-----|-----|-----|
| i | | | j | | k |
sum = (-4) + 0 + 2 = -2
sum < 0,j++
| -4 | -1 | -1 | 0 | 1 | 2 |
|-----|-----|-----|-----|-----|-----|
| i | | | | j | k |
sum = (-4) + 1 + 2 = -1
sum < 0,j++
j == k,回到最新一輪,i++
| -4 | -1 | -1 | 0 | 1 | 2 |
|-----|-----|-----|-----|-----|-----|
| | i | j | | | k |
sum = (-1) + (-1) + 2 = 0,加進集合
j++
k--
| -4 | -1 | -1 | 0 | 1 | 2 |
|-----|-----|-----|-----|-----|-----|
| | i | | j | k | |
sum = (-1) + 0 + 1 = 0,加進集合
j++
k--
j > k,回到最新一輪,i++
| -4 | -1 | -1 | 0 | 1 | 2 |
|-----|-----|-----|-----|-----|-----|
| | | i | j | | k |
i 與上次相同,回到最新一輪,i++
| -4 | -1 | -1 | 0 | 1 | 2 |
|-----|-----|-----|-----|-----|-----|
| | | | i | j | k |
sum = 0 + 1 + 2 = 3
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) {
// 將陣列元素轉成集合再加到大集合內
// 類似這樣的資料結構 [[1, 2, 3], [2, 3, 4]]
s.add(Arrays.asList(nums[i], nums[j], nums[k]));
// 縮小範圍
j++;
k--;
} else if (sum < target) {
j++; // 找更大的元素
} else {
k--; // 找更小的元素
}
}
}
output.addAll(s); // 集合加到陣列裡
return output;
}
}
使用了和 Java 一樣的邏輯執行,換成 Python 的寫法。
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 |
(新手上路,如有錯誤請友善告知,感謝)
Blog
https://chris81051.github.io/2023/06/16/LeetCode-15-3Sum-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論