JavaScript 中的 Two Sum 问题详解及多种解法131

在算法和数据结构的世界中，“Two Sum” 问题是一个经典且频繁出现的题目。它的目标是：给定一个整数数组 `nums` 和一个目标值 `target`，找出数组中两个数之和等于 `target` 的索引。如果有多个答案，返回其中任意一个即可。如果没有两个数的和等于 `target`，则返回一个空数组或者抛出异常，这取决于具体的实现要求。

看似简单的问题，却蕴含着多种解法，每种解法都体现了不同的算法思想和时间复杂度。本文将深入探讨 JavaScript 中解决 Two Sum 问题的多种方法，并分析它们的优缺点。

暴力破解法

最直观的解法是暴力破解法。它通过两层嵌套循环遍历数组中的所有元素对，判断它们的和是否等于 `target`。如果找到符合条件的元素对，则返回它们的索引；否则，遍历完所有元素对后返回空数组。
function twoSumBruteForce(nums, target) {
for (let i = 0; i < ; i++) {
for (let j = i + 1; j < ; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return []; // 未找到符合条件的元素对
}
// 示例用法
const nums1 = [2, 7, 11, 15];
const target1 = 9;
(twoSumBruteForce(nums1, target1)); // Output: [0, 1]
const nums2 = [3, 2, 4];
const target2 = 6;
(twoSumBruteForce(nums2, target2)); // Output: [1, 2]
const nums3 = [3, 3];
const target3 = 6;
(twoSumBruteForce(nums3, target3)); // Output: [0, 1]

暴力破解法的优点在于代码简单易懂，缺点是时间复杂度为 O(n²)，效率较低，对于大型数组，性能会急剧下降。

哈希表法

为了提高效率，我们可以使用哈希表 (JavaScript 中使用 Map 对象) 来存储数组元素及其索引。首先，遍历数组，将每个元素及其索引存入哈希表中。然后，再次遍历数组，对于每个元素，检查 `target - nums[i]` 是否存在于哈希表中。如果存在，则说明找到了两个数之和等于 `target` 的元素对，返回它们的索引；否则，继续遍历。
function twoSumHashMap(nums, target) {
const numMap = new Map();
for (let i = 0; i < ; i++) {
const complement = target - nums[i];
if ((complement)) {
return [(complement), i];
}
(nums[i], i);
}
return []; // 未找到符合条件的元素对
}
// 示例用法 (与暴力破解法示例相同，结果也相同)
(twoSumHashMap(nums1, target1)); // Output: [0, 1]
(twoSumHashMap(nums2, target2)); // Output: [1, 2]
(twoSumHashMap(nums3, target3)); // Output: [0, 1]

哈希表法的优点是时间复杂度为 O(n)，效率比暴力破解法高得多。缺点是需要额外的空间存储哈希表。

优化哈希表法：处理重复元素

上面的哈希表方法在处理包含重复元素的数组时，可能会返回错误的结果。例如，如果数组是 `[3,3]`，目标值是 `6`，则可能返回 `[0,0]` 而不是 `[0,1]`。 我们可以通过在哈希表中存储元素及其所有索引来解决这个问题。
function twoSumHashMapOptimized(nums, target) {
const numMap = new Map();
for (let i = 0; i < ; i++) {
const complement = target - nums[i];
if ((complement)) {
return [(complement)[0], i]; //返回第一个匹配索引
}
if((nums[i])) {
(nums[i]).push(i);
} else {
(nums[i], [i]);
}
}
return []; // 未找到符合条件的元素对
}

这个优化后的版本能够正确处理重复元素的情况。

总结：选择哪种解法取决于具体的应用场景。如果数组规模较小，暴力破解法足够简单易用；如果数组规模较大，则哈希表法具有更高的效率，并且优化后的哈希表法能更稳健地处理各种输入情况。理解这些不同的方法及其优缺点，对于提高算法能力至关重要。 选择合适的算法对于程序的性能优化至关重要，而对算法时间复杂度的理解更是程序员必备的技能。

2025-07-16

上一篇：揭秘黑客常用的JavaScript技巧：从入门到进阶

下一篇：JavaScript数组过滤：深入理解`grep`及其替代方法