LeetCode热题100精讲——Top1:两数之和【哈希】

题目背景

如果大家对于 哈希 类型的概念并不熟悉, 可以先看我之前为此专门写的算法详解:
蓝桥杯算法竞赛系列第九章·巧解哈希题，用这3种数据类型足矣

两数之和

题目链接：两数之和

解题思路：

对于一个元素 nums[i]，想知道有没有另一个元素 nums[j] 的值为 target - nums[i]，这很简单，我们用一个哈希表记录每个元素的值到索引的映射，这样就能快速判断数组中是否有一个值为 target - nums[i] 的元素了.

简单说，数组其实可以理解为一个「索引 -> 值」的哈希表映射，而我们又建立一个「值 -> 索引」的映射即可完成此题.

代码详解：

C++解法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        // 建立值到索引的映射
        unordered_map<int, int> valToIndex;

        for(int i = 0; i < nums.size(); i++)
        {
            // 查哈希表，看是否有能和 nums[i] 凑出 target 的元素
            int need = target - nums[i];
            if(valToIndex.count(need))
            {
                return {i, valToIndex[need]};
            }

            // 存入val->index的映射
            valToIndex[nums[i]] = i;
        }    

        return {-1, -1};
    }
};

Python解法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 建立值到索引的映射表
        valueToIndex = {}

        # 遍历列表
        for i in range(len(nums)):
            # 查哈希表, 看是否有能和nums[i]凑出target的元素
            need = target - nums[i]
            if need in valueToIndex:
                return [i, valueToIndex[need]]
                
            # 将need存入value->index的映射表
            valueToIndex[nums[i]] = i
        
        return [-1, -1]

Python代码也可以使用 enumerate() 方法在循环遍历列表的时候可以得到元素索引以及元素本身:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        valToIndex = {}

        for index, val in enumerate(nums):
            need = target - val
            if need in valToIndex:
                return [index, valToIndex[need]]
            
            valToIndex[val] = index

        return [-1, -1]