「算法刷题」哈希表专题汇总（力扣版）

本文主要记录哈希表的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。

一、设计哈希结构

705. 设计哈希集合（简单难度）

class MyHashSet {
private:
    vector<list<int>> data;// 链表数组
    static const int tableSize = 769;//哈希表的容量,设为static是为了直接初始化
    static int hashFunction(int key) {
        return key % tableSize;
    }
public:
    MyHashSet(): data(tableSize) {}
    void add(int key) {
        int index = hashFunction(key);// 获取key对应的索引
        // 遍历data[h],查看是否已经存在key
        for (auto it = data[index].begin(); it != data[index].end(); it++) {
            if ((*it) == key) {
                return;
            }
        }
        // 如果该key不存在则加入
        data[index].push_back(key);
    }
    void remove(int key){
        int index=hashFunction(key);
        // 遍历data[h],查看是否已经存在key
        for(auto it = data[index].begin(); it != data[index].end(); it++){
            if((*it)==key){
                data[index].erase(it);
                return;
            }
        }
    }

    bool contains(int key) {
        int index = hashFunction(key);
        // 遍历data[h],查看是否已经存在key
        for (auto it = data[index].begin(); it != data[index].end(); it++) {
            if ((*it) == key) {
                return true;
            }
        }
        return false;
    }
};

706. 设计哈希映射（简单难度）

class MyHashMap {
private:
    vector<list<pair<int, int>>> data;// 链表数组,每个链表元素是pair对象
    static const int tableSize = 769;//哈希表的容量,设为static是为了直接初始化
    static int hashFunction(int key) {
        return key % tableSize;
    }
public:
    MyHashMap(): data(tableSize) {}
    
    void put(int key, int value) {
        int h = hashFunction(key);// 获取key对应的索引
        // 遍历data[h],查看是否已经存在key
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                (*it).second = value;
                return;
            }
        }
        // 如果该key不存在则加入
        data[h].push_back(make_pair(key, value));
    }
    
    int get(int key) {
        int h = hashFunction(key);
        // 遍历data[h],查看是否已经存在key
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                return (*it).second;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int h = hashFunction(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                data[h].erase(it);
                return;
            }
        }
    }
};

146. LRU 缓存（中等难度）

剑指 Offer II 031. 最近最少使用缓存（中等难度）

面试题 16.25. LRU 缓存（中等难度）

// 最近最少使用缓存器
class LRUCache {
private:
    int cap;// 容量
    list<pair<int,int>> l;// 链表（队列），存放元素<key,value>的数据
    unordered_map<int, list<pair<int, int>>::iterator> m;//哈希表，用来实现O(1)的查找效率，<key,链表元素指针>
public:
    LRUCache(int capacity):cap(capacity) {}
    // 通过key获取value
    int get(int key) {
        auto it = m.find(key);//在缓存数据中查找
        // 如果没有找到，返回-1
        if (it == m.end()) return -1;
        // 如果成功找到，将其升到链表顶部
        l.splice(l.begin(), l, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = m.find(key);//在缓存数据中查找
        // 如果成功找到，删除原有数据
        if (it != m.end()) l.erase(it->second);
        // 在链表顶部插入新元素
        l.push_front(make_pair(key, value));
        m[key] = l.begin();// 建立哈希映射
        // 如果插入元素后数量大于容量
        if (m.size() > cap) {
            int k = l.rbegin()->first;//找到倒数第一个元素<key,value>的key
            l.pop_back();// 链表删除最后一个元素
            m.erase(k);// 哈希表删除映射
        }
    }
};

380. O(1) 时间插入、删除和获取随机元素（中等难度）

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

/*该题要求实现一个随机集合，其插入、删除和查询的效率都是O(1)
必定需要借助哈希表
*/
class RandomizedSet {
private:
    // 可变数组,可在O(1)内完成获取随机元素操作
    vector<int> nums;
    //哈希表<val,索引>,可在O(1)内完成插入和删除
    unordered_map<int, int> dict;
public:
    RandomizedSet() {
        srand((unsigned)time(NULL));// 设置随机种子，不设置也可以成功
    }
    bool insert(int val) {
        if (dict.count(val)) return false;
        int index = nums.size();
        nums.emplace_back(val);// 向数组中添加
        dict[val] = index;// 向字典中添加
        return true;
    }
    bool remove(int val) {
        if (!dict.count(val)) return false;//val不存在
        int index = dict[val];// 获取val的索引
        // 将数组最后一个元素拷贝到val的位置
        int last = nums.back();// 获取last的值
        nums[index] = last;//将val的位置覆盖为last
        dict[last] = index;//更新last的索引
        // 删除数组最后一个元素
        nums.pop_back();// 移除最后一个元素
        dict.erase(val);// 移除val的映射
        return true;
    }
    int getRandom() {
        int randomIndex = rand()%nums.size();// 取[0,n-1]的随机数
        return nums[randomIndex];
    }
};

二、哈希表的简单难度

1、找出一个序列中某个特殊的数

（1）找出数组中出现次数超过一半的数字

169. 多数元素（简单难度）

剑指 Offer 39. 数组中出现次数超过一半的数字（简单难度）

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 统计nums中每个数组元素出现的频率
        unordered_map<int,int> dict;// nums中每个数，出现频率
        for(int num:nums) dict[num]++;
        //建立哈希数组找其中出现次数大于n/2的数
        int n=nums.size();
        for(auto it=dict.begin();it!=dict.end();++it){
            if(it->second>n/2)
                return it->first;
        }
        return 0;
    }
}

（2）找出数组中只出现一次的数字

136. 只出现一次的数字（简单难度）

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> map;// 数字和出现次数
        // 遍历数组一遍统计频率
        for(int num:nums){map[num]++;}
        // 遍历哈希表
        for(auto it=map.begin();it!=map.end();++it){
            if(it->second==1)
                return it->first;
        }
        return -1;
    }
};

137. 只出现一次的数字 II（中等难度）

剑指 Offer II 004. 只出现一次的数字 （中等难度）

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

剑指 Offer II 070. 排序数组中只出现一次的数字（中等难度）

540. 有序数组中的单一元素（中等难度）

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？

387. 字符串中的第一个唯一字符（简单难度）

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,int> map;// 字符和出现次数
        // 遍历字符串一遍统计频率
        for(char c:s){map[c]++;}
        // 再次遍历遍历字符串
        for(int i=0;i<s.size();++i ){
            if(map[s[i]]==1)
                return i;
        }
        return -1;
    }
};

剑指 Offer 50. 第一个只出现一次的字符（简单难度）

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

点评

class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char,int> map;// 字符和出现次数
        // 遍历字符串一遍统计频率
        for(char c:s){
            map[c]++;
        }
        // 再次遍历遍历字符串
        for(char c:s){
            if(map[c]==1)
                return c;
        }
        return ' ';
    }
};

（3）找出数组中重复的数

217. 存在重复元素（简单难度）

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> dict;
        // 遍历数组
        for(int num:nums){
            if(dict.count(num)<=0) dict[num]++;
            else return true;
        }
        return false;
    }
};

剑指 Offer 03. 数组中重复的数字（简单难度）

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int,int> dict;
        for(int num : nums){
            // 如果已经存在就返回
            if(dict.count(num) > 0) return num;
            // 如果不存在就添加
            else dict[num]++;
        }
        return -1;
    }
};

219. 存在重复元素 II（简单难度）

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> map;// 数字和所在索引
        // 遍历一遍数组元素
        for(int i=0;i<nums.size();++i){
            // 如果当前元素是重复元素
            if(map.count(nums[i])>0){
                //如果满足一次直接返回true
                if(abs(map[nums[i]]-i)<=k){
                    return true;
                }
                //否则更新索引（可能存在2个以上的重复元素）
                else{
                    map[nums[i]]=i;
                }
            }
            map[nums[i]]=i;
        }
        return false;
    }
};

2、找出两个序列中不一样的数

（1）给定1个数组，找出其中在[0,n]中消失的数、

448. 找到所有数组中消失的数字（简单难度）

剑指 Offer 53 - II. 0～n-1中缺失的数字（简单难度）

面试题 17.04. 消失的数字（简单难度）

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        // 统计nums中每个数组元素出现的频率
        unordered_map<int,int> dict;// nums中每个数，出现频率
        for(int num:nums) dict[num]++;

        // 遍历[1, n]，查看不存在的数
        for(int i=1;i<=nums.size();++i){
            if(dict.count(i)<=0)
                res.push_back(i);
        }
        return res;
    }
};

（2）给定2个字符串，找出不一样的字符

389. 找不同（简单难度）

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char,int> dict;
        for(char c:s) dict[c]++;
        for(char c:t){
            // 如果s中存在
            if(dict.count(c)>0){
                // 如果其频率为1，删除其key
                if(dict[c]==1) dict.erase(c);
                // 如果其频率大于1，频率-1
                else dict[c]--;
            }
            // 如果s中不存在，即找到结果
            else{
                return c;
            }
        }
        return ' ';
    }
};

（3）给定2个数组，找出其交集

349. 两个数组的交集（简单难度）

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int,int> dict;
        // 将nums1的元素加入哈希表
        for(auto & num : nums1){
            dict[num]++;
        }
        // 遍历num2
        for(auto & num : nums2){
            // 如果哈希集中有该值，加入结果并删除
            if(dict.count(num)>0) {
                res.push_back(num);
                dict.erase(num);
            }
        }
        return res;//剩下的元素就是
    }
};

350. 两个数组的交集 II（简单难度）

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

使用map容器存储每个数的频率，在该容器中查找是否存在另一个数组的元素

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result_set; // 存放结果
        map<int, int> m;
        //统计每个数的频率
        for (int i : nums1){
            m[i]++;
        }
        //遍历num2中的元素
        for (int num : nums2) {
            // 如果num频率大于0，说明其在nums1中出现过
            if (m[num]>0)
            {
                result_set.push_back(num);//将该num放入结果中
                m[num]--;//频率-1
            }
        }
        return result_set;
    }

（4）给定2个字符串，判断a的字符是否都被b包含

383. 赎金信（简单难度）

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char,int> map;
        //统计magazine中的每个字母频率
        for(int i=0;i<magazine.size();i++){
            map[magazine[i]]+=1;
        }
    	//统计ransomNote中的每个字母频率
        for(int i=0;i<ransomNote.size();i++){
            map[ransomNote[i]]-=1;
        }
        //遍历哈希表，如果某个字母频率小于0，返回false
        for(unordered_map<char,int>::iterator it=map.begin();it!=map.end();it++){
            if(it->second<0)
                return false;
        }
        return true;
    }

（5）给定2个字符串，判断a和b是否是字母异位词

242. 有效的字母异位词（简单难度）

剑指 Offer II 032. 有效的变位词（简单难度）

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

bool isAnagram(string s, string t) {
        unordered_map<char,int> map;
        if(s.size()!=t.size())
            return false;
        //统计s和t中的每个字母频率
        for(int i=0;i<s.size();i++){
            map[s[i]]+=1;
            map[t[i]]-=1;
        }
        //遍历映射表
        for(unordered_map<char,int>::iterator it=map.begin();it!=map.end();it++){
            if(it->second!=0)
                return false;
        }
        return true;
    }

1207. 独一无二的出现次数（简单难度）

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int,int> dict;
        unordered_set<int> set;
        for(int c:arr) dict[c]++;
        for(auto iter:dict){
            if(!set.count(iter.second)) set.insert(iter.second);
            else return false;
        }
        return true;
    }
};

三、哈希表的中等难度

1、特殊规律

409. 最长回文串（简单难度）

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串的长度 。

在构造过程中，请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int> dict;//<字符，频率>
        // 统计字符串中每个字母的频率
        for(char c:s){
            dict[c]++;
        }
        // 查找频率
        int res=0;
        int flag = 0;//是否有中心字符，如果存在奇数个相同字符则可以有
        for(auto it=dict.begin();it!=dict.end();++it){
            // 如果字符频率为偶数个，均可以使用
            if(it->second%2==0){
                res+=it->second;
            }
            // 如果字符频率为奇数个，则丢弃1个，其余的均可使用
            else{
                res+=it->second-1;
                flag = 1;//此时，标记回文串可以有中心点
            }
        }
        return res+flag;//最终结果是偶数部分的最大长度+中心字符
    }
};

202. 快乐数（简单难度）

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1){
            int sum=getSum(n);//求和后的新数
            if(sum==1){
                return true;
            }
            //如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

2、双哈希映射

205. 同构字符串（简单难度）

​ 此题是「290. 单词规律」的简化版，需要我们判断 ss 和 tt 每个位置上的字符是否都一一对应，即 ss 的任意一个字符被 tt 中唯一的字符对应，同时 tt 的任意一个字符被 ss 中唯一的字符对应。这也被称为「双射」的关系。因此，我们维护两张哈希表，第一张哈希表 s2t 以 s 中字符为键，映射至 t 的字符为值，第二张哈希表 t2s 以 tt中字符为键，映射至 s的字符为值。从左至右遍历两个字符串的字符，不断更新两张哈希表，如果出现冲突（即当前下标index 对应的字符 s[index] 已经存在映射且不为t[index] 或当前下标 index 对应的字符 t[index] 已经存在映射且不为s[index]时说明两个字符串无法构成同构，返回false。如果遍历结束没有出现冲突，则表明两个字符串是同构的，返回 true 即可。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> smap;//保存s->t的映射
        unordered_map<char, char> tmap;//保存t->s的映射
        for(int i=0;i<s.size();i++)
        {
            // 如果两个哈希表的映射都不存在，添加数据
            if(smap.count(s[i])<=0&&tmap.count(t[i])<=0)
            {
                smap[s[i]]=t[i];//s->t
                tmap[t[i]]=s[i];//t->s
            }
            // 如果当前字母已经存在并且当前字母和已有映射不同，则返回false
            if(smap.count(s[i])>0&&smap[s[i]]!=t[i]) return false;
            if(tmap.count(t[i])>0&&tmap[t[i]]!=s[i]) return false;
            
        }
        return true;
    }
};

290. 单词规律（简单难度）

class Solution {
public:
    // 分割字符串
    vector<string> splitWord(string str){
        vector<string> words;
        string word;
        // 遍历整个字符串中的字符
        for (char c:str)
            // 如果当前字母为空格并且
            if (c == ' '&&word.size()>0) {
                words.push_back(word);
                word = "";
            } 
            else{
                word += c;
            }
        // 如果word有字符，加入结果
        if (word.size()) words.push_back(word);
        return words;
    }
    bool wordPattern(string pattern, string s) {
        vector<string> words=splitWord(s);
        if(pattern.size()!=words.size())return false;
        // 双哈希法(每个字母和每个单词一一唯一对应)
        unordered_map<string,char> str2ch;// 单词到字母的映射
        unordered_map<char,string> ch2str;// 字母到单词的映射
        // 同时遍历两个序列
        for(int i=0;i<pattern.size();++i){
            char ch=pattern[i]; // 获取当前字母
            string str=words[i];// 获取当前单词
            // 如果当前字母已有映射，检查已有映射和当前单词是否一致
            if(ch2str.count(ch)>0&&ch2str[ch]!=str){
                return false;
            }
            // 如果当前单词已有映射，检查已有映射和当前字母是否一致
            if(str2ch.count(str)>0&&str2ch[str]!=ch){
                return false;
            }
            // 当前字母和当前单词没有映射，建立映射
            ch2str[ch]=str;
            str2ch[str]=ch;
        }
        return true;
    }
};

3、字符串数组找交集

1002. 查找共用字符（简单难度）

多个字符串中对应的字母频次最小值就是常用字符：

//获取一个字符串的各个字母频次
    void getfeq(int * feq,const string &s){
        for(int i=0;i<s.size();i++){
            feq[s[i]-'a']++;
        }
    }
    vector<string> commonChars(vector<string>& words) {
        vector<string> res;
        int minfeq[26] = {0};//最小频次
        getfeq(minfeq,words[0]);//默认第一个字符串为最小
        //循环查找最小频次
        for(int i=1;i<words.size();i++){
            int feq[26] = {0};
            getfeq(feq,words[i]);
            for(int j=0;j<26;j++){
                minfeq[j] = min(minfeq[j],feq[j]);
            }
        }
        // 将统计得到最小频次，转成字符
        for(int i=0;i<26;i++){
            if(minfeq[i]!=0){
                for(int j = 0; j < minfeq[i]; j++){
                    string s(1, i + 'a'); // char -> string
                    res.push_back(s);
                }
            }
        }
        return res;
    }

599. 两个列表的最小索引总和（简单难度）

class Solution {
public:
    // 找两个字符串数组中的交集，并且交集字符串所在的索引和最小
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> dict;//餐厅名字-索引号
        vector<string> res;// 结果数组
        int ans = 2000;//索引和的最大值
        // 遍历数组1,建立哈希映射
        for(int i = 0; i < list1.size(); i++){
            dict[list1[i]]=i;
        }
        // 遍历数组2
        for(int i = 0; i < list2.size(); i++){
            // 如果哈希表中找到了该字符串，说明是和数组1的交集
            auto it =dict.find(list2[i]);
            if(it!=dict.end()){
                int newAns = it->second+i;//新的索引和=该字符串所对应的数组1的索引+i
                // 如果新的索引和更小
                if(newAns  < ans){
                    ans = newAns;//记录该索引和
                    res.clear();// 清空结果字符串
                    res.push_back(list2[i]);
                }
                // 如果新的索引和相等
                else if(newAns== ans){
                    res.push_back(list2[i]);
                }
            }
        }
        return res;
    }
};

49. 字母异位词分组（中等难度）

剑指 Offer II 033. 变位词组（中等难度）

vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string,vector<string>> M;//<排序后的字符串，乱序的字符串数组>
    	// 遍历字符串数组，将每个字符串排序
        for(int i=0;i<strs.size();i++){
            //先对排序
            string key=strs[i];
            sort(key.begin(),key.end());
            //哈希表添加元素
            M[key].push_back(strs[i]);
        }
        //遍历哈希表，将其value加入结果数组
        for(unordered_map<string,vector<string>>::iterator iter=M.begin();iter!=M.end();iter++){
            res.push_back(iter->second);
        }
        return res;
    }

四、子串/子序列/子数组

1、前缀和+哈希表

560. 和为 K 的子数组（中等难度）

剑指 Offer II 010. 和为 k 的子数组（中等难度）

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res = 0;// 结果，连续子数组的个数
        // 初始化哈希表
        unordered_map<int, int> dict; // <前缀和,次数>
        dict[0] = 1;//
        // 遍历计算前缀和
        int preSum = 0;// 前缀和
        for (int num:nums) {
            preSum += num;
            // 哈希表中存在
            if (dict.count(preSum - k) >0) {
                res += dict[preSum - k];
            }
            // 哈希表中不存在，则新建
            ++dict[preSum];
        }
        return res;
    }
};

2、滑动窗口+哈希表

3. 无重复字符的最长子串（中等难度）

剑指 Offer 48. 最长不含重复字符的子字符串

剑指 Offer II 016. 不含重复字符的最长子字符串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> dict;// <字符，频率>
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int right=-1;
        int res=0;
        // 枚举左指针的位置，初始值隐性地表示为 -1
        for(int left=0;left<s.length();++left){
            if(left!=0) dict.erase(s[left-1]);
            // 当右指针下一步没有到达数组右边界且右指针下一步没有重复，不断地移动右指针
            while(right+1<s.length()&&!dict.count(s[right+1])){
                dict[s[right+1]]++;
                right++;
            }
            // 第 left 到 right 个字符是一个最长的无重复字符子串
            res = max(res, right - left + 1);
        }
        return res;
    }
};

438. 找到字符串中所有字母异位词（中等难度）

剑指 Offer II 015. 字符串中的所有变位词（中等难度）

vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        //判断条件
        if(s.size()<p.size())
            return res;
        int l = 0;//负责记录每次字母异位词的起始位置
        int r = 0;//不断循环
        //记录频率的哈希表
        vector<int> freq_s(26, 0), freq_p(26, 0);
        // 初始化代码值
        for( int i = 0 ; i < p.size() ; i++ ){
            freq_p[p[i] - 'a' ]++;//统计p中每个字母出现的频率
            freq_s[s[r++] - 'a' ]++;//统计s中前段字母出现的频率
        }
        //如果字母频率相等
        if ( freq_s == freq_p )
            res.push_back( l );
        // 固定长度的滑动窗口
        while(r < s.size()){
            freq_s[s[r++] - 'a' ]++;//新一段字母的频率
            freq_s[s[l++] - 'a' ]--;//旧窗口字母的频率
            if ( freq_s == freq_p )
                res.push_back( l );
        }
        return res;
    }

3、子序列

128. 最长连续序列（中等难度）

剑指 Offer II 119. 最长连续序列（中等难度）

[最长连续序列

哈希

代码简洁易懂 【c++/java版】 - 最长连续序列 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/ha-xi-zui-qing-xi-yi-dong-de-jiang-jie-c-xpnr/)

class Solution {
public:
    // 注意子序列，最长连续子序列不包含重复元素
    int longestConsecutive(vector<int>& nums) {
        int res=0;
        // 统计每个数字频率，达到去重功能
        unordered_map<int,int> dict;
        for(int num:nums) dict[num]++;
        // 遍历所有数字，已经经过去重
        for(int num:nums){
            int cur=num;//以x为起点
            // 避免重复枚举一段x+1为起点的序列
            if(!dict.count(cur-1)){
                // 查询x+1，x+2,...,x+y是否存在
                while(dict.count(cur+1))
                    cur++;
            }
            // 本次查询的[x,y]的长度为y-x+1
            res=max(res,cur-num+1);
        }
        return res;
    }
};

674. 最长连续递增序列（简单难度）

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int res=1;//只有1个数的情况
        int count = 1;
        // 遍历所有数字(大于1个数的情况)
        for(int i=1;i<nums.size();++i){
            // 避免重复枚举一段x+1为起点的序列
            if(nums[i-1]<nums[i]){
                count++;
            }
            else {
                count=1;
            }
            // 本次查询的[x,y]的长度为y-x+1
            res=max(count,res);
        }
        return res;
    }
};

五、哈希表处理数字之和

1. 两数之和（简单难度）

创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashmap;//哈希映射:nums[i]->i
        // 遍历整个数组
        for (int i = 0; i < nums.size(); ++i) {
            // 如果哈希表中存在该映射，直接返回结果
            if (hashmap.count(target - nums[i]) >0) {
                return {i,hashmap[target - nums[i]]};
            }
            // 如果哈希表中不存在该映射，加入该映射
            hashmap[nums[i]] = i;
        }
        return {};
    }
};

剑指 Offer 57. 和为s的两个数字

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left=0;//左指针
        int right=nums.size()-1;//右指针
        int sum=0;
        while(left<=right){
            sum=nums[left]+nums[right];
            // 如果两数和==target，直接返回
            if(sum==target) return {nums[left],nums[right]};
            // 如果两数和>target，说明应该降低两数和，右指针左移即可
            else if(sum>target) right--;
            // 如果两数和<target，说明应该增加两数和，左指针右移即可
            else left++;
        }
        return {nums[left],nums[right]};
    }
};

15. 三数之和（中等难度）

1.将数组排序 2.定义三个指针，i，j，k。遍历i，那么这个问题就可以转化为在i之后的数组中寻找nums[j]+nums[k]=-nums[i]这个问题，也就将三数之和问题转变为二数之和—（可以使用双指针）

class Solution {
public:
    /*题目要求答案不重复，并且i,j,k是三个不同的数
    只要保证i<=j<=k,并且每重循环中都去重i,j,k就可以保证答案不重复
    i正序遍历，j正序遍历，k反序遍历，因为i固定时，j增加，k减少才能得到相同的和*/
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());//排序数组
        // 循环遍历
        int n = nums.size();
        int low, high, twoSum, tmp;// i+low+high=0
        // 固定i,[0,n-3]，写成i<n也可以通过
        for (int i=0;i<n-2;++i) {
            if (i>0&&nums[i]==nums[i-1]) continue;// 防止第1个数i重复
            // 正序遍历low，反序遍历high
            low=i+1,high=n-1,twoSum = -nums[i];
            while(low<high){
                tmp=nums[low]+nums[high];
                if(tmp>twoSum)high--;
                else if(tmp<twoSum) low++;
                else{
                    res.push_back({nums[i], nums[low], nums[high]});
                    low++;high--;// 防止第二与第三个数重复
                    while(low<high&&nums[low]==nums[low-1])low++;
                    while(low<high&&nums[high]==nums[high+1])high--;
                }
            }
        }
        return res;
    }
};

18、四数之和（中等难度）

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());  // 从小到大排序
        int n = nums.size();
        int low, high, twoSum, tmp;// i+j+low+high=0,low+high=twoSum
        // 枚举i,[0,n-1]
        for(int i=0;i<n-3; i++) {
            if(i>0&&nums[i]==nums[i-1]) continue;  // 防止第1个数i重复
            // 枚举j,[i+1,n-1]
            for(int j=i+1; j<n-2;j++) {
                if (j>i+1&&nums[j]==nums[j-1]) continue;  // 防止第2个数j重复
                low=j+1, high=n-1, twoSum=target-nums[i]-nums[j];
                while(low<high) {
                    tmp = nums[low]+nums[high];
                    if (tmp>twoSum) high--;// 如果low+high大,high--
                    else if (tmp<twoSum) low++;// 如果low+high小,low--
                    else {
                        // 添加结果
                        res.push_back({nums[i], nums[j], nums[low], nums[high]});
                        low++, high--;  // 防止第三与第四个数重复
                        while(low<high&&nums[low]==nums[low-1])low++;
                        while(low<high&&nums[high]==nums[high+1])high--;
                    } 
                }
            }
        }
        return res;
    }
};

454、四数之和II（中等难度）

这道题的数据量不大，0 ≤ N ≤ 500，但是如果使用暴力解法，四层循环，会超时。这道题的思路和第 1 题思路也类似，先可以将 2 个数组中的组合都存入 map 中。之后将剩下的 2 个数组进行 for 循环，找出和为 0 的组合。这样时间复杂度是 O(n^2)。当然也可以讲剩下的 2 个数组的组合也存入 map 中，不过最后在 2 个 map 中查找结果也是 O(n^2) 的时间复杂度。

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
        // 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        int count = 0; // 统计a+b+c+d = 0 出现的次数
        // 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }