반응형
문제
[LeetCode][Javascirpt] 15번 - 3Sum
배열에서 3개의 수를 더했을 때 0이 되는 경우를 배열에 저장해서 리턴해 줘야 하는 문제
3개의 수는 ([-1,0,1], [-1,0,1])과 중복되어 들어 있으면 안 된다.
코드 설명
실패 코드
- 경우의 수만큼만 반복문을 돌게 하고 싶었는데 딱히 기억이 안 나서 반복문으로 풀었다.
- for문을 중첩해서 3개 쓰면 복잡도가 기본적으로
O(N^3)
이다. - 근데 for문을 돈다고 해서 필요한 경우의 수만 반복문을 도는 것은 아니다. 그래서 문제이다.
- 문제의 예제 배열은 경우의 수가 아래와 같다. 하지만 for문의 경우 모든 경우를 돌게 되어 중복한 값이 결과로 나올 수 있다.
0 1 2
0 1 3
0 1 4
0 1 5
1 2 3
1 2 4
1 2 5
2 3 4
2 3 5
3 4 5
const threeSum = nums => {
let result = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
let zeroArray = [nums[i], nums[j], nums[k]];
if (zeroArray.reduce((k, v) => k + v) === 0) {
if (
result.length >= 1 &&
!zeroArray.every((v, i) => result[result.length - 1][i] === v)
) {
result.push(zeroArray);
} else if (result.length === 0) {
result.push(zeroArray);
}
}
}
}
}
성공 코드
- j, k라는 변수에 for문을 도는 변수 i+1, nums.length - 1의 값을 넣어 줌으로써 for문 2개를 줄였다.
while (j < k)
조건을 부여함으로써 j와 k는 중간 지점에 만나 멈출 것이다. 그러면 불필요한 반복을 할 필요도 없어지게 된다.
const threeSum = nums => {
const results = [];
if (nums.length < 3) return results;
nums = nums.sort((a, b) => a - b);
let target = 0;
for (let i = 0; i < nums.length - 2; i++) {
if (nums[i] > target) break;
if (i > 0 && nums[i] === nums[i - 1]) continue;
let j = i + 1;
let k = nums.length - 1;
while (j < k) {
let sum = nums[i] + nums[j] + nums[k];
if (sum === target) {
results.push([nums[i], nums[j], nums[k]]);
while (nums[j] === nums[j + 1]) j++;
while (nums[k] === nums[k - 1]) k--;
j++;
k--;
} else if (sum < target) {
j++;
} else {
k--;
}
}
}
return results;
};
반응형