[数据结构与算法][LeetCode刷题笔记]1 - 两数之和（哈希表）

一、题目描述

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

示例：

提示：

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

思考：

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

复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。