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

[LeetCode刷题笔记]1 - 两数之和（哈希表）

news 来源：原创 2024/4/27 20:55:58

一、题目描述

给定一个整数数组 nums 和一个整数目标值 target，需要在该数组中找出 和为目标值 target 的两个整数，并返回它们的数组下标。
注意：
- 数组中同一个元素在答案里不能重复出现；
- 保证每个输入仅仅对应一个答案，不存在没有答案的情况；
- 返回两个下标的顺序可以任意；

示例：

输入	输出
$n u m s = [2, 7, 11, 15], t a r g e t = 9$	$[0, 1]$
$n u m s = [3, 2, 4], t a r g e t = 6$	$[1, 2]$
$n u m s = [3, 3], t a r g e t = 6$	$[0, 1]$

提示：

$2 <= nums.length <= 10^4$
$10^9 <= nums[i] <= 10^9$
$10^9 <= target <= 10^9$
只会存在一个有效答案

思考：

暴力做法，两层循环。时间复杂度为 $O(n^2)$ ，不可取；
循环第一个数，第二个数进行二分查找。时间复杂度为 $O (n l o g n)$ ，但存在一个问题，要进行排序（ $O (n l o g n)$ ），且排完序后下标错乱了，需要用一个 pair数组 去存原始下标，比较麻烦；
循环第一个数，第二个数用哈希表（map/unordered_map）进行查找。时间复杂度为 $O (n l o g n)$ 或者 $O (n)$ ；

二、求解思路：哈希表（unordered_map）

思路

建立一个哈希表，存储的键为数组中的值，值为数组中该值的下标；
遍历数组中每个元素的下标 i，查找另一个元素的下标 j，使得下标对应的两数之和等于 target。
- 查找另一个元素的方法可以用哈希表来找，即用 h.count(target - nums[i]) 函数查找;
- 当查找失败时，元素 nums[i] 一定不可能是答案，则将其加入到哈希表中，即 h[nums[i]] = i;
- 当查找成功时，将答案返回即可，即 return {h[r], i}。

C++代码

class Solution {
public:

    #define fi first
    #define se second

    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> h;  // 哈希表键值对存储的是 值：下标
        for (int i = 0; i < nums.size(); ++i) {
            int r = target - nums[i];
            // 查找是否存在值为r的键值对，有的话就返回，没有的话把它加近哈希表
            if (h.count(r)) return {h[r], i};
            h[nums[i]] = i;
        }
        return {};
    }
};