JS求解两数之和算法详解

什么是两数之和算法？

两个整数的和就是将这两个数加起来得到的数。而两数之和算法是指在给定一组整数的情况下，找到其中两个数之和等于给定目标值的两个数。

算法的实现步骤

1. 循环遍历整个数列，固定一个数，得到另一个数。
2. 在剩下的数列中循环查找另一个数（目标值减去当前数），如果查找到，则说明找到了答案。
3. 返回两个数的下标。

代码示例1

下面是这个算法的一个简单实现示例，它演示了如何在给定的整数数组中找到两个数之和等于给定目标值：

function twoSum(nums, target) {
    for (var i = 0; i < nums.length; i++) {
        for (var j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
}

我们根据上述代码，定义数组：

let nums = [2, 7, 11, 15];
let target = 9;

进行函数调用：

console.log(twoSum(nums, target));

输出结果为 [0, 1]，这证明了这个算法的正确性。

代码示例2

下面是对算法进行优化，增加一个哈希表来加快查找速度：

function twoSum(nums, target) {
    var map = {};
    for (var i = 0; i < nums.length; i++) {
        var complement = target - nums[i];
        if (map.hasOwnProperty(complement)) {
            return , i];
        }
        map[nums[i]] = i;
    }
}

同样，我们根据上述代码，定义数组：

let nums = [3, 2, 4];
let target = 6;

进行函数调用：

console.log(twoSum(nums, target));

输出结果为 [1, 2]，也证明了优化后的算法的正确性。

总结

两数之和算法是一个比较基础的算法，是大多数初学者接触的第一个算法之一。理解了这个算法，可以让我们更好的理解和学习其他算法。在实际开发中，我们可以根据不同的场景选择不同的实现方式。