算法(19)-两数之和

哈希表

 2024/03/11 

题目(easy)

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

思路

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(log n)	O(log n)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

本题适合用 Map。

const twoSum = (nums, target) => {
    const hash = {};
    for(let i = 0; i < nums.length; i++) {
        if (hash[target - nums[i]] !== undefined) {
            return [i, hash[target - nums[i]]];
        }
        hash[nums[i]] = i;
    }
    return [];
}

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/11/2024-03-11-%E7%AE%97%E6%B3%95(19)-%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C/

发表日期：March 11th 2024, 3:38:33 pm

更新日期：March 17th 2024, 3:48:33 pm

Next Post

算法(20)-四数相加II
Previous Post

算法(18)-快乐数

CATALOG

1. 题目(easy)
2. 思路