forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathwogha95.js
More file actions
60 lines (52 loc) ยท 1.47 KB
/
wogha95.js
File metadata and controls
60 lines (52 loc) ยท 1.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
* TC: O(N^2)
* SC: O(N)
*
* ํ์ด
* 2sum์ ํ์ฅ ๋ฌธ์ (nums[i] == nums[j] + nums[k])
* 2sum์ ํฌํฌ์ธํฐ๋ก ์๊ฐ๋ณต์ก๋ O(N)์ ๋ง๋ค๊ธฐ ์ํด ํฌํฌ์ธํฐ๋ฅผ ํ์ฉํ๋ค.
*/
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const result = [];
const sortedNums = nums.sort((a, b) => a - b);
// 3๊ฐ ํญ์ ํฉ์ด 0์ด ๋ ์ ์๋ ๊ฒฝ์ฐ
if (sortedNums[0] > 0 || sortedNums[sortedNums.length - 1] < 0) {
return [];
}
// 1. ์ํ๋ฅผ ํ๋ฉฐ 2sum์ target ๊ฐ์ ์ง์ ํจ
for (let index = 0; index < sortedNums.length - 2; ) {
twoSum(index + 1, sortedNums[index]);
// 3. ๋์ผํ ์ซ์๋ฅผ ์ ์ธํ๊ธฐ ์ํด ์ํ
while (sortedNums[index] === sortedNums[index + 1]) {
index += 1;
}
index += 1;
}
return result;
function twoSum(startIndex, target) {
let left = startIndex;
let right = sortedNums.length - 1;
// 2. ํฌํฌ์ธํฐ๋ก 2sum์ด target์ด ๋๋ ๊ฒฝ์ฐ๋ฅผ ์ฐพ๊ธฐ ์ํด ์ํ
while (left < right) {
const sum = sortedNums[left] + sortedNums[right];
if (sum + target === 0) {
result.push([target, sortedNums[left], sortedNums[right]]);
}
if (sum + target < 0) {
while (sortedNums[left] === sortedNums[left + 1]) {
left += 1;
}
left += 1;
} else {
while (sortedNums[right] === sortedNums[right - 1]) {
right -= 1;
}
right -= 1;
}
}
}
};