原题地址：两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
暴力循环
直接对数组进行双重循环，找出所有可能的组合：
// js实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum1 = function(nums, target) {
for (let i = 0; i < nums.length - 1; i ++) {
for (let j = i + 1; j < nums.length; j ++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
};
# python3实现
class Solution1:
@staticmethod
def twoSum(nums: List[int], target: int) -> List[int]:
for i in range(0, len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
测试：
let start = new Date();
const test = twoSum1;
console.log(test([2, 7, 11, 15], 9)); // [ 0, 1 ]
console.log(test([3, 3], 6)); // [ 0, 1 ]
console.log(new Date().getTime() - start.getTime()); // 10
时间复杂度： 进行了双重循环，所以时间复杂度为$O(n^2)$
空间复杂度： 空间复杂度为$O(1)$
哈希
利用map(python中为dict)将遍历过的值和索引存储起来，后续判断时直接在通过map即可判断前面有没有符合条件的数据。由于map(dict)随机访问的时间复杂度为O(1)，所以相比暴力循环法可以更快地得到结果。
// js实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum2 = function(nums, target) {
let map = new Map();
for (let i = 0; i < nums.length; i ++) {
// 通过在map中查找与nums[i]之和为target的key，即可找到目标值
if (map.has(target - nums[i])) {
return [map.get(target - nums[i]), i]
}
// 将遍历过值和索引存储到map中，注意key为值，value为索引
map.set(nums[i], i)
}
return [];
};
# python3实现
class Solution2:
@staticmethod
def twoSum(nums: List[int], target: int) -> List[int]:
_dict = {}
for i in range(0, len(nums)):
# 通过在dict中查找与nums[i]之和为target的key，即可找到目标值
if target - nums[i] in _dict:
return [_dict[target - nums[i]], i]
# 将遍历过值和索引存储到dict中，注意key为值，value为索引
_dict[nums[i]] = i
return []
测试：
let start = new Date();
const test = twoSum2;
console.log(test([2, 7, 11, 15], 9)); // [ 0, 1 ]
console.log(test([3, 3], 6)); // [ 0, 1 ]
console.log(new Date().getTime() - start.getTime()); // 6
相比暴力循环方法，速度有了一定提升
时间复杂度： 只需要循环一次，map取值的时间复杂度为$O(1)$，所以整体时间复杂度为$O(n)$
空间复杂度： 需要额外的map来存储遍历过的数据，空间复杂度为$O(n)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Mar 13,2021