[LeetCode] #18. 4Sum
題目
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na, b, c,anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == targetYou may return the answer in any order.
直覺解
構想：
找出所有可能的組合，刪掉重複的組合，然後回傳答案。
javascript 實作：
const fourSum = function(nums, target) {
let a = 0
let b = 1
let c = 2
let d = 3
const result = []
while (a < nums.length - 3) {
while (b < nums.length -2) {
while (c < nums.length -1) {
while (d < nums.length) {
if (nums[a] + nums[b] + nums[c] + nums[d] === target) {
let isDuplicated = false
const array = [nums[a], nums[b], nums[c], nums[d]].sort((a, b) => a - b)
for (const item of result) {
if (
array[0] === item[0]
&& array[1] === item[1]
&& array[2] === item[2]
&& array[3] === item[3]
) {
isDuplicated = true
break
}
}
if (!isDuplicated) {
result.push(array)
}
}
d++
}
c++
d = c + 1
}
b++
c = b + 1
d = c + 1
}
a++
b = a + 1
c = b + 1
d = c + 1
}
return result
}
效能：
Runtime: 488 ms, faster than 13.20% of JavaScript online submissions for 4Sum.
Memory Usage: 42.2 MB, less than 37.39% of JavaScript online submissions for 4Sum.
犯過的錯誤：
- 踩到「物件不能直接比較」的坑
參考別人的解後，javascript 實作優化：
構想：如果組合是重複的，就跳過去不再進行計算。這樣最後還可以省下「去除重複的組合」的步驟
const fourSum = function(nums, target) {
let a = 0
let b = 1
let left = 2
let right = nums.length - 1
const result = []
nums.sort((a, b) => a - b)
for (let a = 0; a < nums.length - 3; a++) {
if (
a != 0 && nums[a] == nums[a - 1]
) {
continue
}
for (let b = a + 1; b < nums.length - 2; b++) {
if (
b != a + 1
&& nums[b] === nums[b - 1]
) {
continue
}
let left = b + 1
let right = nums.length - 1
while (left < right) {
if (
left !== b + 1
&& nums[left] === nums[left - 1]
) {
left++
continue
}
const sum = nums[a] + nums [b] + nums[left] + nums[right]
if (sum === target) {
result.push([nums[a], nums[b], nums[left], nums[right]])
left++
} else if (sum < target) {
left++
} else {
right--
}
}
}
}
return result
}
效能：
Runtime: 104 ms, faster than 74.32% of JavaScript online submissions for 4Sum.
Memory Usage: 40.4 MB, less than 69.30% of JavaScript online submissions for 4Sum.
犯過的錯誤：
- 「如果組合是重複的，就跳過去不再進行計算」真是一件精細的事情，一不小心就會把正確的組合也跳過去了⋯⋯
研究別人的解
來源：
JavaScript Solution kSum using twoSum
別人的 javascript 實作：
const fourSum = (nums, tar) => {
nums.sort((a, b) => a - b);
return kSum(nums, tar, 0, 4);
};
const kSum = (nums, tar, start, k) => {
const res = [];
if (start === nums.length || nums[start] * k > tar || tar > nums[nums.length - 1] * k) return res;
if (k === 2) return twoSum(nums, tar, start);
for (let i = start; i < nums.length; i++) {
if (i === start || nums[i] !== nums[i - 1]) {
for (let set of kSum(nums, tar - nums[i], i + 1, k - 1)) {
set.push(nums[i]);
res.push(set);
}
}
}
return res;
};
const twoSum = (nums, tar, start) => {
const res = [];
const set = new Set();
for (let i = start; i < nums.length; i++) {
if (!res.length || res[res.length - 1][1] !== nums[i])
if (set.has(tar - nums[i])) res.push([tar - nums[i], nums[i]]);
set.add(nums[i]);
}
return res;
};
效能：
Runtime: 96 ms, faster than 92.40% of JavaScript online submissions for 4Sum.
Memory Usage: 44.8 MB, less than 22.24% of JavaScript online submissions for 4Sum.
研究過程：
先把 nums 排序，以利在之後的計算中，盡快離開不可能的答案候選者，節省運算時間。把 four sum 簡化成 two sum，用遞迴的方式計算答案。在 two sum 階段時，用 set 紀錄檢查過的數字（而不是使用雙指針逼近 target）。計算時會跳過重複的組合。
參考別人的解，自己用 javascript 實作：
版本一：two sum 的地方用 hash table 紀錄檢查過的值。
const fourSum = function(nums, target) {
nums = nums.sort((a, b) => a - b)
return kSum(nums, target, 4)
}
function kSum (nums, target, k) {
const result = []
if (
nums.length < k
|| nums[0] * k > target
|| nums[nums.length - 1] * k < target
) { return result }
if (k === 2) {
return twoSum(nums, target)
}
nums.forEach((n, index) => {
if (index === 0 || n !== nums[index - 1]) {
const answers = kSum(nums.slice(index + 1), target - n, k - 1)
answers.forEach(ans => result.push([n, ...ans]))
}
})
return result
}
function twoSum (nums, target) {
const seen = {}
const result = []
const length = nums.length
for (let i = 0; i < length; i++) {
if (
i > 2
&& nums[i] === nums[i - 1]
&& nums[i - 1] === nums[i - 2]
) {
continue
}
const different = target - nums[i]
if (seen[different] || seen[different] === 0) {
result.push([nums[i], nums[seen[different]]])
delete seen[different]
} else {
seen[nums[i]] = i
}
}
return result
}
效能：
Runtime: 224 ms, faster than 17.86% of JavaScript online submissions for 4Sum.
Memory Usage: 54.3 MB, less than 5.14% of JavaScript online submissions for 4Sum.
犯過的錯誤：
- 「如果組合是重複的，就跳過去不再進行計算」沒有設好條件，仍然出現了重複的組合。
- 因為沒有善加利用「nums 已經排序過了」的狀況，去提早脫離不可能的組合，導致「Runtime 1836 ms, Memory 98.4 MB」這種令人汗顏的效能⋯⋯
版本二：two sum 的地方用雙指針逼近 target。因為其他部分是一樣的，所以底下只列出 function twoSum 的部分。
function twoSum (nums, target) {
const result = []
let left = 0
let right = nums.length - 1
while (left < right) {
if (left !== 0 && nums[left] === nums[left - 1]) {
left++
continue
}
if (nums[left] + nums[right] === target) {
result.push([nums[left], nums[right]])
left++
} else if (nums[left] + nums[right] < target) {
left++
} else {
right--
}
}
return result
}
效能：
Runtime: 96 ms, faster than 92.14% of JavaScript online submissions for 4Sum.
Memory Usage: 44.9 MB, less than 20.29% of JavaScript online submissions for 4Sum.
Comments
Post a Comment