两数之和

这个问题是经典的两数之和问题，有多种解法可以实现。下面提供三种主要解法：暴力法、哈希表法和双指针法（适用于有序数组）。

方法一：暴力法

暴力法是最直接的方法，通过两层嵌套循环来检查每一对元素是否满足和为目标值。

步骤：

1. 遍历数组中的每一个元素 nums[i]。
2. 对于每个元素，再次遍历数组的剩余元素 nums[j]，检查 nums[i] + nums[j] 是否等于 target。
3. 如果找到这样一对元素，返回它们的索引。

代码：

function twoSum(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 [];
}

时间复杂度：O(n^2)，因为我们有两个嵌套循环。

空间复杂度：O(1)，因为我们只使用了常数级别的额外空间。

方法二：哈希表法

使用哈希表可以将查找时间从 O(n) 降到 O(1)，从而使整体时间复杂度降到 O(n)。

步骤：

1. 创建一个空的哈希表 map。
2. 遍历数组中的每一个元素 nums[i]。
3. 在哈希表中检查 target - nums[i] 是否存在。如果存在，返回当前元素和 target - nums[i] 的索引。
4. 如果不存在，将当前元素 nums[i] 及其索引存入哈希表。

代码：

function twoSum(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)。

空间复杂度：O(n)，因为最坏情况下哈希表中存储了所有元素。

方法三：双指针法（适用于有序数组）

如果数组是有序的，可以使用双指针法解决问题。双指针法利用两个指针从数组两端向中间移动，根据和的大小调整指针位置。

步骤：

1. 将数组和其索引一起存入一个数组并排序。
2. 使用两个指针 left 和 right 分别指向数组的两端。
3. 计算 nums[left] + nums[right] 的和：
   • 如果和等于 target，返回两个指针的索引。
   • 如果和小于 target，移动 left 指针。
   • 如果和大于 target，移动 right 指针。

代码：

function twoSum(nums, target) {
    const numsWithIndex = nums.map((num, index) => ({ num, index }));
    numsWithIndex.sort((a, b) => a.num - b.num);

    let left = 0;
    let right = numsWithIndex.length - 1;

    while (left < right) {
        const sum = numsWithIndex[left].num + numsWithIndex[right].num;
        if (sum === target) {
            return [numsWithIndex[left].index, numsWithIndex[right].index];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [];
}

时间复杂度：O(n log n)，因为排序的时间复杂度是 O(n log n)。

空间复杂度：O(n)，因为我们存储了额外的数组。

总结

• 暴力法适合小规模数据，简单直接。
• 哈希表法是最常用的方法，适合一般情况，时间复杂度较低。
• 双指针法适用于已排序数组或可以对数组进行排序的情况，空间复杂度更低。

以上三种方法各有优劣，可以根据实际需求选择合适的方法。