算法题：两数之和

题目

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

**输入：**nums = [2,7,11,15], target = 9 输出：[0,1] **解释：**因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

**输入：**nums = [3,2,4], target = 6 输出：[1,2]

示例 3：

**输入：**nums = [3,3], target = 6 输出：[0,1]

自己的解法

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

AI帮我改进解法

1. 双重循环的效率低下

• 你的解法使用了双重循环（for 循环），这意味着时间复杂度是 O(n2)O(n^2)O(n2)，其中 n 是数组的长度。当 nums 数组非常大时，性能可能会受到影响。
• 此方法会遍历所有可能的数对并判断它们是否满足条件。虽然能解决问题，但并不是最优解。

2. 使用两次相同的元素

• 在你的解法中，j 会遍历数组的所有元素，包括 i。但是题目要求不能使用两次相同的元素。如果你不加检查，i == j 时，nums[i] + nums[j] 会等于目标，但它们是同一个元素，这会导致错误结果。
• 你已经使用了 i != j 的条件来避免这个问题，但这个条件应该考虑到双重循环中的索引顺序，防止重复的对 (i,j) 被返回。

3. 改进：哈希表解法

• 哈希表解法（也称为字典法）是一个常见的更高效的解决方案。时间复杂度为 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);  // 如果差值没有，存储当前数字和索引
    }
};
 

reference