15. 3Sum
Leetcode
https://leetcode.com/problems/3sum/description/
題目
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 1:
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.Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105
解答
方法一
3Sum 只要固定一個數後，剩下的兩個數就是 1. Two sum 的解法，所以我們先用這個方法解解看，但 3Sum 最後要的答案是矩陣中的元素不能重複，所以最後還需要多判斷 3 個值加起的矩陣，是否已經出現過 (checkNotDuplicate)
var threeSum = function(nums) {
const output = [];
const checkIsSame = (arr1, arr2) => {
for(let i=0; i<arr1.length; i++) {
if (arr1[i] !== arr2[i]) {
return false;
}
}
return true;
}
const checkNotDuplicate = (arr) => {
for(let i=0; i<output.length; i++) {
if (checkIsSame(arr, output[i])) {
return false;
};
}
return true;
}
for (let i=0; i<nums.length; i++) {
const x = nums[i];
const map = {};
for (let j=i+1; j<nums.length; j++) {
const y = nums[j];
const z = -(x + y);
if (map[z] !== undefined) {
const result = [x, y, z];
result.sort();
if(checkNotDuplicate(result)) {
output.push(result);
};
}
map[y] = j;
}
}
return output;
};但可惜的是遇到測資 [0,0,0,0,0,0,0,0,...] 數萬個 0，或是符合結果的 output 矩陣數量很多時， checkNotDuplicate 的計算會越來越多導致 TLE...
方法二 - 排序 + HashTable
方法一的失敗點在於重複數值的檢查太多遍導致 TLE，要如何把重複數值移掉呢？我們可以採用以下方式：
由小到大先排序過原始矩陣，即
nums[x] < nums[y] < nums[z]在對每個元素處理時，只需要處理第一次出現的元素就好，例如：
[-2, -2, -2, -2, 1, 1]，只有第一個元素的-2需要處理，後面不論再出現幾次-2都可以略過了
var threeSum = function (nums) {
nums.sort((a, b) => a - b);
const output = [];
for (let i = 0; i < nums.length; i++) {
// 步驟 2. 排除後續出現過的元素
if (i > 0 && nums[i] === nums[i - 1]) continue;
const x = nums[i];
const map = {};
for (let j = i + 1; j < nums.length; j++) {
// 步驟 2. 排除後續出現過的元素
if (j - 1 !== i && nums[j] === nums[j - 1]) continue;
const y = nums[j];
const z = -(x + y);
if (map[z] !== undefined) {
const result = [x, y, z];
output.push(result);
}
map[y] = j;
}
}
return output;
};但將以上這段程式碼拿去跑，會發現有個問題是測資: [0, 0, 0] ，如果此時 i=0, j=1 當跑到 if (map[z] !== undefined) 這行時，因為 0 還沒有被加進 map 裡，所以 if 的判斷式不會進去，而接著 i=0, j=2 以及 i=1, j=2 時，因為會排除掉後續出現過的元素，所以迴圈也不會再進去了，最後 output 會錯誤的回傳空矩陣
爲了解決這個問題我們需要改變一下 map 參數記錄的邏輯：
把
map從第一個迴圈中移出，改為在最外層記錄mapmap從原本紀錄 鍵值對(key, value) 改為紀錄 元素的次數，這樣一來在最後 3 個數相加判斷是否為 0 的時候，可以從map得知需要用的值是否足夠例如：
[-2, 1, 1]，map會先記錄-2有一個、1有兩個，前兩個元素計算時根據x=-2, y=1推斷出z=1，y, z兩個都需要1，這時查看map發現裡面1的數量有兩個是足夠的，所以[-2, 1, 1]就會是其中一組答案
var threeSum = function (nums) {
nums.sort((a, b) => a - b);
const output = [];
const map = {};
// 先遍歷矩陣一次，記錄所有元素的個數
for (let i = 0; i < nums.length; i++) {
const value = nums[i];
if (map[value] === undefined) {
map[value] = 1
} else {
map[value]++
}
}
for (let i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
const x = nums[i];
for (let j = i + 1; j < nums.length; j++) {
if (j - 1 !== i && nums[j] === nums[j - 1]) continue;
const y = nums[j];
const z = 0 - x - y;
const result = [x, y, z];
// 預期的元素不在 map 中，可以直接略過
if (map[z] === undefined) continue;
let countZ = 1;
if (x === z) countZ++;
if (y === z) countZ++;
// 確認元素的個數足夠 => 答案成立
if (map[z] >= countZ) {
output.push(result);
}
}
}
return output;
};但這樣我們會發現答案還是有重複的
例如：[-4, -1, -1, 0, 1, 2]
從第二個元素 -1 開始算答案有 [-1, 0, 1]
從第四個元素 0 開始算答案也有 [0, 1, -1]
所以其實我們還需要以下邏輯移除掉重複的答案：
以上從第四個元素
0開始算，預期的第三個答案是-1，但這個數已經小於第二個元素1了，由於一開始的矩陣已經由小到大排序過，所以可以知道[0, 1, -1]一定是個重複的答案了，需要略過
另外由於矩陣已經由小到大排序過，所以答案的 3 個數字正負號會是 --+ 或是 -++, 第一個數字一定不會是正數，所以也可以略過第一個元素大於 0 的狀況優化執行速度
var threeSum = function (nums) {
nums.sort((a, b) => a - b);
const output = [];
const map = {};
for (let i = 0; i < nums.length; i++) {
const value = nums[i];
if (map[value] === undefined) {
map[value] = 1
} else {
map[value]++
}
}
for (let i = 0; i < nums.length; i++) {
// 排除第一個數字為正數的狀況，優化執行速度
if (nums[i] > 0) break;
if (i > 0 && nums[i] === nums[i - 1]) continue;
const x = nums[i];
for (let j = i + 1; j < nums.length; j++) {
if (j - 1 !== i && nums[j] === nums[j - 1]) continue;
const y = nums[j];
const z = 0 - x - y;
const result = [x, y, z];
// 因為矩陣由小到大排序，排除第三個元素小於第二個元素的重複答案
if (z < y) continue;
if (map[z] === undefined) continue;
let countZ = 1;
if (x === z) countZ++;
if (y === z) countZ++;
if (map[z] >= countZ) {
output.push(result);
}
}
}
return output;
};Runtime: 261 ms Beats 22.75% of users with JavaScript
Memory: 67.37 MB Beats 10.12% of users with JavaScript
參考資料
Solution 1. Hashtable
方法三 - 排序 + Two pointers
由於打算把原始的矩陣由小到大排序過，所以在找 第二(y) 及 第三(z) 個數字時可以使用 雙指針的方式(l 代表左、r 代表右) 求出來，這裡有幾個需要注意的地方：
由於答案要排除重複數組，所以在找到答案後，如果
l+1的元素跟l的元素一樣的話，要繼續往右邊的下一個元素l+2找 (r也是同樣的道理)
var threeSum = function (nums) {
nums.sort((a, b) => a - b);
const output = [];
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] === nums[i - 1]) continue;
const x = nums[i];
let l = i + 1;
let r = nums.length - 1;
while (l < r) {
const y = nums[l];
const z = nums[r];
if (x + y + z === 0) {
output.push([x, nums[l], nums[r]]);
// 找到答案後如果下一個數字一樣，繼續往右找
while (l < r && nums[l + 1] === nums[l]) {
l++;
}
while (l < r && nums[r - 1] === nums[r]) {
r--;
}
l++;
r--;
} else if (x + y + z > 0) {
r--;
} else {
l++;
}
}
}
return output;
};Runtime: 145 ms Beats 88.80% of users with JavaScript
Memory: 64.37 MB Beats 62.95% of users with JavaScript
參考資料
Last updated
Was this helpful?