1
2
3
4
5
6
7
8
9
10
11
12
13
14
| const twoSum = (nums, target) => {
const len = nums.length;
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
};
const nums = [3, 2, 4];
const target = 7;
twoSum(nums, target);
|
上面时间复杂度为 O(n^2)，以空间换时间，可将时间复杂度优化到 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
| const twoSum = (nums, target) => {
const cache = {};
for (let i = 0; i < nums.length; i++) {
let value = [nums[i]];
let diff = target - value;
if (typeof cache[value] === 'undefined') {
cache[diff] = i;
} else {
return [cache[value], i];
}
}
};
|