两数之和

这是 LeetCode 上最经典的题目，也是很多程序员梦开始的地方。

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

解题思路

1. 暴力法 (Brute Force)

最直观的方法是使用两层循环。

// 时间复杂度: O(n^2)
var twoSum = function(nums, target) {
    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 [];
};

2. 哈希表 (Hash Table)

为了降低时间复杂度，我们可以使用哈希表来存储已经遍历过的数字及其下标。 这样，对于每个数字 x，我们只需要检查 target - x 是否在哈希表中即可。

// 时间复杂度: O(n)
var twoSum = function(nums, target) {
    const map = new Map();
    
    for(let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if(map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
};

总结

使用空间换时间的思想，将查找时间从 $O(n)$ 降低到 $O(1)$，是算法优化中非常常见的策略。