forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsounmind.js
More file actions
60 lines (50 loc) Β· 1.73 KB
/
sounmind.js
File metadata and controls
60 lines (50 loc) Β· 1.73 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
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const sorted = nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < sorted.length; i++) {
const fixedNumber = sorted[i];
const previousFixedNumber = sorted[i - 1];
if (fixedNumber === previousFixedNumber) {
continue;
}
let [leftEnd, rightEnd] = [i + 1, sorted.length - 1];
while (leftEnd < rightEnd) {
const sum = fixedNumber + sorted[leftEnd] + sorted[rightEnd];
if (sum === 0) {
result.push([sorted[leftEnd], sorted[rightEnd], sorted[i]]);
while (
sorted[leftEnd + 1] === sorted[leftEnd] ||
sorted[rightEnd - 1] === sorted[rightEnd]
) {
if (sorted[leftEnd + 1] === sorted[leftEnd]) {
leftEnd += 1;
}
if (sorted[rightEnd - 1] === sorted[rightEnd]) {
rightEnd -= 1;
}
}
leftEnd += 1;
rightEnd -= 1;
} else if (sum < 0) {
leftEnd += 1;
} else {
rightEnd -= 1;
}
}
}
return result;
};
/**
* Time Complexity: O(n^2)
* The algorithm involves sorting the input array, which takes O(n log n) time.
* The main part of the algorithm consists of a loop that runs O(n) times, and within that loop, there is a two-pointer technique that runs in O(n) time.
* Thus, the overall time complexity is O(n log n) + O(n^2), which simplifies to O(n^2).
*
* Space Complexity: O(n)
* The space complexity is O(n) due to the space needed for the sorted array and the result array.
* Although the sorting algorithm may require additional space, typically O(log n) for the in-place sort in JavaScript, the dominant term is O(n) for the result storage.
*/