「算法刷题」哈希表的前缀和、滑动窗口的LeetCode题目实现

[TOC]

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

一、子串/子序列/子数组的LeetCode题目

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;
    }
};

二、哈希表处理数字之和的LeetCode题目

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 {};
    }
};

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

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

vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;//结果
        std::sort(nums.begin(),nums.end());//排序数组
        // 循环遍历
        for (int i = nums.size()-1; i >= 2; ){
            // 循环遍历left和right
            for (int left = 0, right = i-1; left < right; ){
                int tmp_sum = nums[left]+nums[right];
                // 如果两数之和小则移动左边界
                if (tmp_sum < -nums[i]){
                    left++;
                } 
                // 如果两数之和大则移动右边界
                else if (tmp_sum > -nums[i]){
                    right--;
                }
                // 如果两数之和符合则记录该答案 
                else {
                    vector<int> v = {nums[left], nums[right], nums[i]};
                    result.push_back(v);
                    //去重复 left
                    do{
                        left++;
                    } while (left < right && nums[left-1] == nums[left]);
                    //去重复 right
                    do{
                        right--;
                    } while (left < right && nums[right+1] == nums[right]);
                }
            }
            //去重复 c
            do{
                i--;
            } while (i >= 2 && nums[i+1] == nums[i]);
        }
        return result;
    }

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

vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;// 结果数组
        sort(nums.begin(), nums.end());
        // 遍历数组
        for (int k = 0; k < nums.size(); k++) {
            // 这种剪枝是错误的，这道题目target 是任意值
            // if (nums[k] > target) {
            //     return result;
            // }
            // 去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 正确去重方法
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    if (nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    } else if (nums[k] + nums[i] + nums[left] + nums[right] < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 去重逻辑应该放在找到一个四元组之后
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }

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;
    }