两数之和

#算法/哈希 #leetcode #2024/07/28

目录

题目

image.png600

题目重点

  • 返回下标
  • 复杂度小于 O(n^2)
  • 可能会重复，比如[3,3]

思路

  • 思路一：排序思路，数组排序后双指针会更好，但会破坏原数组索引，题设中需要返回下标
  • 思路二：哈希存储

代码实现

错题一

image.png600

想着两个 for 逻辑更清晰，但有两个问题，如下图： image.png600

错误二

image.png600

标准答案

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {

    // 维护 val-index 的 map
    let valToIndexMap = new Map();

    // 遍历每个元素是否存在，这样的组合
    for (let i = 0; i < nums.length; i++) {
        let need = target - nums[i];
        if (valToIndexMap.has(need)) {
            // 存在，直接返回
            return [valToIndexMap.get(need), i];
        }
        // 之前的记录到 map 里， 供后续元素检查
        valToIndexMap.set(nums[i], i);
    }

    // 不存在，返回 null
    return null;

};

参考