-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path001-twoSum.js
More file actions
57 lines (53 loc) · 1.61 KB
/
001-twoSum.js
File metadata and controls
57 lines (53 loc) · 1.61 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
/*
* 【two sum】
* Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
*/
var twoSum = function(nums, target) {
var len = nums.length;
var result = [];
for(var i=0; i<len; i++){
var s = target - nums[i];
for(var j=i+1; j<len; j++){
if(nums[j] == s){
return [i,j];
}
}
}
return "No two sum solution";
};
console.log(twoSum([2,7,11,15], 9)); // 时间-O(n²)、空间-O(1)
/*
Problem：https://leetcode.com/problems/two-sum/#/description
Submission Details： https://leetcode.com/submissions/detail/102422716/
Solution：https://leetcode.com/articles/two-sum/
*/
// 其他方法1
var twoSum1 = function (nums, target) {
var map = {};
for (var i = 0; i < nums.length; i++) {
map[nums[i]] = i;
}
for (var i = 0; i < nums.length; i++) {
var complement = target - nums[i];
if (map[complement] && map[complement] != i) {
return [i, map[complement] ];
}
}
return "No two sum solution";
};
console.log(twoSum1([2,7,11,15], 9)); // 时间-O(n)、空间-O(n)
// 其他方法2
var twoSum2 = function (nums, target) {
var map = {};
for (var i = 0; i < nums.length; i++) {
var complement = target - nums[i];
if (map[complement]) {
return [map[complement]-1, i ];
}
map[nums[i]] = i+1; // key的键值为0时，上面的if会验证不过，+1矫正。return的时候再-1
}
return "No two sum solution";
};
console.log(twoSum2([2,7,11,15], 9)); // 时间-O(n)、空间-O(n)