/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
if (!nums || !nums.length) return [];
const map = {};
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
const diff = target - num;
if (diff in map) return [map[diff], i];
map[num] = i;
}
};
Python Code
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hashmap = {}
for i, n in enumerate(nums):
diff = target - n
if diff in hashmap:
return [hashmap[diff], i]
hashmap[n] = i
C++ Code
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> seen;
for (int i = 0; i < nums.size(); i++) {
int sub = target - nums[i];
auto it = seen.find(sub);
if (it != seen.end()) {
return {it->second, i};
}
seen[nums[i]] = i;
}
return {};
}
};
方法 2：排序+双指针
思路
先给数组排序，再用双指针查找。
不过题目要求返回下标，所以排序之前还需要保存原本的下标。
复杂度分析
时间复杂度：$O(NlogN)$，N 为数组长度。
空间复杂度：$O(N)$。
代码
JavaScript Code
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
if (!nums || !nums.length) return [];
// 保存原来的下标，然后升序排序，nums 中元素的格式是 [num, index]
// [2,7,11,15] => [[2, 0], [7, 1], [11, 2], [15, 3]]
nums = nums.map((n, i) => [n, i]);
nums.sort((a, b) => a[0] - b[0]);
let l = 0,
r = nums.length - 1;
while (l < r) {
const n1 = nums[l][0],
n2 = nums[r][0];
if (n1 + n2 === target) return [nums[l][1], nums[r][1]];
// 太大了，右指针左移
if (n1 + n2 > target) r--;
// 太小了，左指针右移
else l++;
}
};
方法 3：暴力法
思路
暴力法也顺便做一下吧。
复杂度分析
时间复杂度：$O(N^2)$，N 为数组长度。
空间复杂度：$O(1)$。
代码
JavaScript Code
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
if (!nums || !nums.length) return [];
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];
}
}
};