[21/08/24 KATA NINJA] leetcode #4
4sum
少し遅い様子です.
次は、改善されていないソリューションコードです.
加速xコード
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
let answer = {};
nums = nums.sort((a, b) => a - b);
for (let i = 0; i <= nums.length - 4; i++) {
for (let j = nums.length - 1; j >= i + 3; j--) {
let k = i + 1;
let l = j - 1;
while (k < l) {
const r = nums[i] + nums[k] + nums[l] + nums[j];
if (r < target) {
k++;
} else {
if (r === target) {
answer[`${nums[i]},${nums[k]},${nums[l]},${nums[j]}`] = [nums[i],nums[k],nums[l],nums[j]];
k++;
l--;
} else {
l--;
}
}
}
}
}
return Object.keys(answer).map(key=>answer[key]);
};
アクセラレータコード
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
let answer = {};
nums = nums.sort((a, b) => a - b);
let lastI;
for (let i = 0; i <= nums.length - 4; i++) {
// 이전의 nums[i] 값과 같다면, 건너뛰어도댐 같은 과정을 반복되게 할 뿐임.
if(lastI === nums[i]) continue;
let lastJ;
for (let j = nums.length - 1; j >= i + 3; j--) {
// 이전의 nums[j] 값과 같다면, 건너뛰어도댐 같은 과정을 반복되게 할 뿐임.
if(nums[j] === lastJ) continue;
let k = i + 1;
let l = j - 1;
while (k < l) {
const r = nums[i] + nums[k] + nums[l] + nums[j];
if (r < target) {
lastK = nums[k];
k++;
} else {
if (r === target) {
answer[`${nums[i]},${nums[k]},${nums[l]},${nums[j]}`] = [nums[i],nums[k],nums[l],nums[j]];
lastK = nums[k];
lastL = nums[l];
k++;
l--;
} else {
lastL = nums[l];
l--;
}
}
}
lastJ = nums[j]
}
lastI = nums[i];
}
return Object.keys(answer).map(key=>answer[key]);
};
注意しなければならない事実
while (k < l) {
while(nums[k] === lastK) {
k++;
}
while(nums[l] === lastL) {
l--
}
// 반복문의 조건에 들어가는 변수들을 반복문안에서 늘리거나 줄였으면 조건을 한번더 체킹해주어야함.
if(k>=l) break;
Reference
この問題について([21/08/24 KATA NINJA] leetcode #4), 我々は、より多くの情報をここで見つけました
https://velog.io/@rat8397/210824-leetcode-4
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
let answer = {};
nums = nums.sort((a, b) => a - b);
for (let i = 0; i <= nums.length - 4; i++) {
for (let j = nums.length - 1; j >= i + 3; j--) {
let k = i + 1;
let l = j - 1;
while (k < l) {
const r = nums[i] + nums[k] + nums[l] + nums[j];
if (r < target) {
k++;
} else {
if (r === target) {
answer[`${nums[i]},${nums[k]},${nums[l]},${nums[j]}`] = [nums[i],nums[k],nums[l],nums[j]];
k++;
l--;
} else {
l--;
}
}
}
}
}
return Object.keys(answer).map(key=>answer[key]);
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
let answer = {};
nums = nums.sort((a, b) => a - b);
let lastI;
for (let i = 0; i <= nums.length - 4; i++) {
// 이전의 nums[i] 값과 같다면, 건너뛰어도댐 같은 과정을 반복되게 할 뿐임.
if(lastI === nums[i]) continue;
let lastJ;
for (let j = nums.length - 1; j >= i + 3; j--) {
// 이전의 nums[j] 값과 같다면, 건너뛰어도댐 같은 과정을 반복되게 할 뿐임.
if(nums[j] === lastJ) continue;
let k = i + 1;
let l = j - 1;
while (k < l) {
const r = nums[i] + nums[k] + nums[l] + nums[j];
if (r < target) {
lastK = nums[k];
k++;
} else {
if (r === target) {
answer[`${nums[i]},${nums[k]},${nums[l]},${nums[j]}`] = [nums[i],nums[k],nums[l],nums[j]];
lastK = nums[k];
lastL = nums[l];
k++;
l--;
} else {
lastL = nums[l];
l--;
}
}
}
lastJ = nums[j]
}
lastI = nums[i];
}
return Object.keys(answer).map(key=>answer[key]);
};
while (k < l) {
while(nums[k] === lastK) {
k++;
}
while(nums[l] === lastL) {
l--
}
// 반복문의 조건에 들어가는 변수들을 반복문안에서 늘리거나 줄였으면 조건을 한번더 체킹해주어야함.
if(k>=l) break;
Reference
この問題について([21/08/24 KATA NINJA] leetcode #4), 我々は、より多くの情報をここで見つけました https://velog.io/@rat8397/210824-leetcode-4テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol