forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHoonDongKang.ts
More file actions
56 lines (45 loc) Β· 1.7 KB
/
HoonDongKang.ts
File metadata and controls
56 lines (45 loc) Β· 1.7 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
/**
* [Problem]: [001] Two Sum
* (https://leetcode.com/problems/two-sum/description/)
*/
function twoSum(nums: number[], target: number): number[] {
// μκ° λ³΅μ‘λ O(n^2)
// κ³΅κ° λ³΅μ‘λ O(1)
function doubleLoopFunc(num: number[], target: number): number[] {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
return [];
}
// μκ° λ³΅μ‘λ O(n)
// κ³΅κ° λ³΅μ‘λ O(n)
function differenceMap(nums: number[], target: number): number[] {
const diffMap = new Map<number, number>();
for (let [i, num] of nums.entries()) {
const diff = target - num;
if (diffMap.has(diff)) return [i, diffMap.get(diff)!];
diffMap.set(num, i);
}
return [];
}
// μκ° λ³΅μ‘λ O(nlog n) - sort
// κ³΅κ° λ³΅μ‘λ O(1)
// μ λ ¬μ ν΅ν΄ μΈλ±μ€ κ°μ μ μ§ν μ μμ΄μ μ€ν¨
// μΈλ±μ€ κ°μ΄ μλ λ°°μ΄μ μμλ₯Ό λ°ννλ λ¬Έμ μμλ μ¬μ©μ΄ κ°λ₯ν λ―?
function twoPointerFunc(nums: number[], target: number): number[] {
nums.sort((a, b) => a - b);
let leftPointer = 0;
let rightPointer = nums.length - 1;
while (leftPointer < rightPointer) {
const twoSum = nums[leftPointer] + nums[rightPointer];
if (twoSum === target) return [leftPointer, rightPointer];
if (twoSum < target) leftPointer++;
if (twoSum > target) rightPointer--;
}
return [];
}
return twoPointerFunc(nums, target);
}
console.log(twoSum([2, 7, 11, 15], 9));