当前位置：首页 > article >正文

【哈希】1. leetcode 1. 两数之和

article 2025/3/15 3:10:08

1 题目描述

题目链接：两数之和
在这里插入图片描述

2 题目解析

一般的思维：找到两个数A和B，判断A和B相加是否为target。
我们可以采用逆向思维：找到一个数A，在nums数组中找是否有值等于target - A，因为题目要求只返回一个组合即可，因此就可以在找到之后直接return返回。

在这里插入图片描述
将不满足条件的都丢入哈希表中。
以前是从前往后找，现在是从后往前找。

3 代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int, int> hash;

        for (int i = 0; i < nums.size(); ++ i)
        {
            int x = target - nums[i];   //根据nums[i],找nums中是否有值为x --> 逆向思考
            if (hash.count(x))
                return {hash[x], i};
            
            //如果没有找到就建立哈希映射
            hash[nums[i]] = i;
        }

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