JavaScript 两数之和详解：算法、优化与应用12

在程序员的日常工作中，算法题是不可避免的一部分，而“两数之和”（Two Sum）问题则是其中最基础、最经典的问题之一。这个问题看似简单，但其背后蕴含着多种解法和优化技巧，对于理解算法设计和数据结构具有重要的意义。本文将深入探讨 JavaScript 中解决“两数之和”问题的各种方法，并分析其时间复杂度和空间复杂度，最终帮助你掌握这个重要算法。

问题描述: 给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复使用相同的元素。

示例:

输入: nums = [2,7,11,15], target = 9
输出: [0,1]
因为 nums[0] + nums[1] == 9

方法一：暴力枚举法

最直观的方法是使用暴力枚举法，即遍历数组中的每一个元素，然后与其他元素进行两两相加，判断是否等于目标值。代码如下：
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 []; // 没有找到满足条件的两个数
}

该方法的时间复杂度为 O(n²)，空间复杂度为 O(1)。对于较小的数组，该方法运行速度较快，但当数组规模较大时，其效率会急剧下降。

方法二：哈希表法

为了提高效率，我们可以使用哈希表（JavaScript 中使用 Map 对象）来存储数组元素及其下标。遍历数组时，对于每个元素，我们查找 `target - nums[i]` 是否存在于哈希表中。如果存在，则找到了目标值对应的两个元素；如果不存在，则将该元素及其下标添加到哈希表中。
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 [];
}

该方法的时间复杂度为 O(n)，空间复杂度为 O(n)。由于哈希表的查找时间复杂度为 O(1)，因此该方法的效率远高于暴力枚举法。在大多数情况下，哈希表法是解决“两数之和”问题的最佳方法。

方法三：排序后双指针法

如果允许修改原数组，我们可以先对数组进行排序，然后使用双指针法来查找目标值。一个指针指向数组的起始位置，另一个指针指向数组的末尾位置。如果两个指针指向的元素之和等于目标值，则找到了目标值对应的两个元素；如果小于目标值，则将左指针右移；如果大于目标值，则将右指针左移。此方法需要额外的排序步骤。
function twoSumSort(nums, target) {
const sortedNums = [...nums].sort((a, b) => a - b); // 创建副本并排序
let left = 0;
let right = - 1;
while (left < right) {
const sum = sortedNums[left] + sortedNums[right];
if (sum === target) {
// 需要找到原始数组中的索引
const index1 = (sortedNums[left]);
const index2 = (sortedNums[right]); // 处理重复元素
return index1 !== index2 ? [index1, index2] : [(sortedNums[left],index1+1), index1];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}

该方法的时间复杂度为 O(n log n)（排序的时间复杂度），空间复杂度为 O(log n) 或 O(n) （取决于排序算法）。虽然时间复杂度不如哈希表法，但在特定情况下，例如需要对排序后的数组进行其他操作时，该方法可能更有效率。

总结:

本文介绍了三种解决 JavaScript “两数之和”问题的常用方法：暴力枚举法、哈希表法和排序后双指针法。哈希表法通常是效率最高的方法，其时间复杂度为 O(n)，空间复杂度为 O(n)。选择哪种方法取决于具体情况，需要考虑数组大小、是否允许修改原数组以及其他相关因素。理解这些不同的方法能够帮助你更好地掌握算法设计和数据结构，为解决更复杂的算法问题打下坚实的基础。记住，选择合适的算法对于程序的性能至关重要。

2025-06-02

上一篇：JavaScript NPS：提升用户满意度的神器与最佳实践

下一篇：JavaScript字典：对象、Map与性能优化详解