一、哈希表

核心解题思维总结

1. 两数之和：在数组中寻找两个元素满足特定条件（和为目标值）
   • 核心思路：通过 "互补值" 建立元素间的联系，用哈希表存储已遍历元素，实现快速查找
   • 思维拓展：这是 "空间换时间" 思想的典型应用
2. 字母异位词分组：将具有相同特征（字母组成相同）的元素归类
   • 核心思路：为同类元素设计统一的 "标识"（排序后的字符串或字符计数），以此作为分组依据
   • 思维拓展：学会为不同元素设计 "特征码"，将复杂问题转化为分组问题
3. 最长连续序列：在无序数据中寻找最长的连续关系
   • 核心思路：通过哈希表快速判断元素连续性，或通过排序将无序转为有序后线性扫描
   • 思维拓展：边界判断很重要（如序列起点的判定、重复元素的处理）

哈希表的适用场景

当遇到以下情况时，优先考虑使用哈希表（unordered_map/unordered_set）：

1. 需要快速查找元素：哈希表的查找时间复杂度为 O (1)，远快于数组的 O (n)
   • 例：两数之和中查找互补数，最长连续序列中判断元素是否存在
2. 需要键值对映射关系：当需要存储 "元素 - 索引"、"特征 - 集合" 等对应关系时
   • 例：字母异位词分组中 "排序字符串 - 原字符串集合" 的映射
3. 需要去重操作：unordered_set会自动去重，适合处理包含重复元素的场景
   • 例：最长连续序列中先去重，避免重复计算
4. 时间复杂度要求高：当题目要求 O (n) 时间复杂度时，哈希表是常用工具

C++ 新手必学的 STL 容器与函数

1. 容器类：
   • vector：动态数组，最常用的序列容器
     • 常用操作：push_back()添加元素、size()获取长度、empty()判断是否为空
   • unordered_map：哈希表（键值对）
     • 常用操作：find(key)查找键、[key]访问 / 设置值、begin()/end()遍历
   • unordered_set：哈希集合（仅存储键）
     • 常用操作：insert()添加元素、find()查找元素、count()判断元素是否存在
   • pair：存储两个关联数据（如排序法中的 "值 - 索引"）
     • 访问方式：first获取第一个元素、second获取第二个元素
2. 算法函数：
   • sort()：排序函数（需包含<algorithm>头文件）
     • 用法：sort(begin, end)，默认升序排序
     • 例：sort(str.begin(), str.end())对字符串排序
   • max()/min()：获取两个值中的最大 / 最小值
     • 例：max_length = max(max_length, current_length)

新手常见问题与解决方法

1. 容器初始化：
   • 用数组初始化集合：unordered_set<int> s(nums.begin(), nums.end())
2. 哈希表遍历：

for (auto& pair : map) {  // auto自动推断类型为pair<key_type, value_type>

    key = pair.first;    // 获取键

    value = pair.second; // 获取值

}

1. 处理边界情况：
   • 空数组：if (nums.empty()) return ...
   • 重复元素：用unordered_set去重或在循环中跳过
2. 时间与空间权衡：
   • 哈希表通常用 O (n) 空间换取 O (n) 时间
   • 排序法通常用 O (n log n) 时间换取 O (1) 空间

1.两数之和

最简单就是两个for循环，不过时间复杂度是O(N^2)

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        int n = nums.size();

        for(int i = 0; i < n; i++){

            for(int j = i + 1; j < n; j++){

                if(nums[i] + nums[j] == target){

                    return {i, j};

                }

            }

        }

        return {};

    }

};

另外一种方法是排序+双指针，先排序之后两个指针往中间走，所指的两个值的和与target值只可能有三种情况，根据情况移动前后指针即可。

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        vector<pair<int, int>> indexNums;   //声明有序对

        for(int i = 0; i < nums.size(); i++){

            // emplace_back是一个直接在容器中创建对象的方法，速度快

            indexNums.emplace_back(nums[i], i); //排序会打乱索引所以需要记录一下原索引

        }

        sort(indexNums.begin(), indexNums.end());

        int left = 0, right = indexNums.size() - 1;

        while(left < right){

            //获取第一个/第二个元素

            int currentSum = indexNums[left].first + indexNums[right].first;

            if(currentSum == target){

                return {indexNums[left].second, indexNums[right].second};

            }

            else if(currentSum < target){

                left++;

            }

            else{

                right--;

            }

        }

        return {};

    }

};

不过最快的还是用哈希表。我们现在是需要求x+y=target，那么y就等于target-x，这样子的话就只需要找target-x的值在哪里就可以了

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        //unorder_map是哈希表，存储键值对，查找速度快，内部无需存储

        //在这里索引是nums的值，值是nums的索引

        unordered_map<int, int> numMap;

        for(int i = 0; i < nums.size(); i++){

            int complement = target - nums[i];

            //找nummap里有没有complement值，如果有的话直接范围索引complement对应的值（nums元素的索引）

            //find返回迭代器（类似指针），没找到就会返回表尾end

            if(numMap.find(complement) != numMap.end()){

                return{i, numMap[complement]};

            }

            //如果find结果是end，就意味着哈希表里没有complement这个值，那就先把现在的nums[i]存到哈希表里，让nums[i]作为索引，i作为对应的值

            numMap[nums[i]] = i;

        }

        return {};

    }

};

49.字母异位词分组

这个比较好想，把每个词排序，如果是字母异位词，排序结果是一样的。创建一个哈希表，把排序的结果作为键，把原字符串组成的一个vector作为值。这样子输出的结果和要求一样。

class Solution {

public:

    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        //创建哈希表，键是排序后的字符串，值是该组所有字母异位词

        unordered_map<string, vector<string>> groups;

        //范围遍历，遍历每个字符串

        for(string s: strs){

            string key = s;

            sort(key.begin(), key.end());

            //将原字符串添加到对应的分组中，如果key不存在，就会自动创建新的键值对

            groups[key].push_back(s);

        }

        vector<vector<string>> result;

        //基于引用的遍历，遍历哈希表，将所有分组添加到结果中

        for(auto& pair: groups){

            result.push_back(pair.second);

        }

        return result;

    }

};

第二种方法是计数法，依次遍历字符串，创一个26位数组记录每个字符串字母出现次数，把这26个字母的出现次序转成一个字符串作为键，把原字符串作为值。最后只需要提取出来里边的值返回即可。

class Solution {

public:

    vector<vector<string>> groupAnagrams(vector<string>& strs) {

       

        unordered_map<string, vector<string>> groups;

        for(string s: strs){

            //初始化数组，统计每个单词字母出现的次数

            int count[26] = {0};

            for(char c: s){

                //获得0-25的索引

                count[c - 'a']++;

            }

            //将计数数组转化为哈希表的键

            //比如aab转换成210000000····

            string key;

            for(int i = 0; i < 26; i++){

                //防止混淆，在每一个数字前加一个#

                //比如11，可能是aa 也可能是是11个a

                key += '#' + to_string(count[i]);

            }

            //将原字符串添加到对应分组里

            groups[key].push_back(s);

        }

        vector<vector<string>> result;

        for(auto& pair: groups){

            result.push_back(pair.second);

        }

        return result;

    }

};

128.最长连续序列

最好用的就是哈希表，这里用哈希表存储一下数字是否出现，这里用了unordered_set方法，能够给数组排序和去重。之后就可以开始遍历这个序列，有一个需要注意的是我们其实只需要从每个序列的起点开始计算，所以如何判断一个点是不是起点呢？你可以直接判断num-1存不存在即可。如何判断这个序列到头了呢？判断num+1是否存在即可。遍历期间记录当前数字和当前长度，每次遍历数组之后就把当前长度和最大长度作比较即可。

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

        //题目中个数为0的情况

        if(nums.empty()) return 0;

        //unordered_set是哈希集合的一个容器，可以直接用数组初始化，且【排序+自动去重】

        unordered_set<int> num_set(nums.begin(), nums.end());

        int max_length = 0;

        //遍历numset的元素

        for(int num: num_set){

            //此处优化的点就是每次只从序列起点开始计算

            //如果发现num-1没有，那么也就意味着num是该序列的起点

            if(num_set.find(num - 1) == num_set.end()){

                int current_num = num;

                int current_length = 1;

                //往后继续遍历，如果currentnum+不等于end，即currentnum+1存在，那就可以继续往后遍历

                while(num_set.find(current_num +1) != num_set.end()){

                    current_num++;

                    current_length++;

                }

                //一直遍历到currentnum+1不存在，即该序列结束，要开始找下一个序列的起点

                //对比已经获得的当前长度和最大长度

                max_length = max(max_length, current_length);

            }

        }

        return max_length;

    }

};

第二种方法就很容易想到。直接对序列进行排序，相同的数字跳过，和上一个数字连续的话长度就增加，不连续就重置长度重新开始比。

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

        if(nums.empty()) return 0;

       

        sort(nums.begin(), nums.end());

        int max_length = 1;

        int current_length = 1;

       

        for(int i = 1; i < nums.size(); i++){

            //跳过相同的数字

            if(nums[i] == nums[i - 1]){

                continue;

            }

            //如果num和上一个num是连续的，当前长度就+1

            else if(nums[i] == nums[i - 1] + 1){

                current_length++;

            }

            //如果和上一个不连续，那就结束本轮遍历，对比最大长度，重置当前长度

            else{

                max_length = max(max_length, current_length);

                current_length = 1;

            }

        }

        //最后比一次（可能序列在数组末尾）

        max_length = max(max_length, current_length);

        return max_length;

    }

};

二、双指针

核心解题思维总结

1. 移动零：将数组中特定元素（0）移动到一端，保持其他元素顺序
   • 核心思路：双指针分离元素（非零元素放前，零元素放后），避免额外空间
   • 思维拓展：双指针可用于 "分离不同类型元素" 的场景，如 "将奇数放前偶数放后"
2. 盛最多水的容器：寻找最优边界组合以最大化面积
   • 核心思路：利用双指针从两端向中间移动，通过贪心策略（移动较短边界）优化搜索
   • 思维拓展："短板效应" 在优化问题中的应用，通过移动劣势端寻找更优解
3. 三数之和：在数组中寻找满足特定条件（和为 0）的不重复三元组
   • 核心思路：排序 + 双指针，固定一个元素后转化为两数之和问题，重点处理去重
   • 思维拓展：多指针技术可将高复杂度问题（O (n³)）降为低复杂度（O (n²)）
4. 接雨水：计算凹槽能存储的水量总和
   • 核心思路：每个位置的储水量由左右两侧最高边界决定，通过不同方法（双指针 / 动态规划 / 单调栈）计算边界
   • 思维拓展：从 "局部最优" 到 "全局最优" 的推导，多方法可解决同一问题

二、双指针技巧的进阶应用

双指针是这几道题的核心技术，总结其常见用法：

1. 同向双指针（如移动零）：
   • 慢指针记录有效位置，快指针遍历寻找有效元素
   • 适用场景：元素分离、移除特定元素、数组去重等
2. 反向双指针（如盛最多水的容器、三数之和）：
   • 左右指针从两端向中间移动，通过条件判断决定移动哪一侧
   • 适用场景：寻找最优组合、两数 / 三数之和等
3. 双指针的优势：
   • 降低时间复杂度（通常从 O (n²) 降至 O (n)）
   • 减少额外空间使用（通常为 O (1) 空间复杂度）

三、关键算法思想

1. 贪心算法：
   • 应用：盛最多水的容器中移动较短边界，接雨水双指针法中优先处理较低一侧
   • 核心：每一步都做局部最优选择，最终得到全局最优解
2. 排序的作用：
   • 便于去重（如三数之和中跳过相同元素）
   • 为双指针创造条件（有序数组才能通过移动指针调整和的大小）
   • 注意：排序会改变元素原始位置，适合不要求返回原始索引的问题
3. 去重技巧：
   • 排序后通过相邻元素比较去重（nums[i] == nums[i-1]）
   • 处理多个维度的去重（如三数之和中需对三个元素分别去重）

四、C++ 新手必学知识点

1. 容器操作进阶：
   • 二维 vector：vector<vector<int>>用于存储多组结果（如三数之和的三元组）
   • 栈（stack）：push()入栈、pop()出栈、top()取栈顶元素（如接雨水的单调栈法）
   • 常用操作：push_back()添加元素、size()获取长度、empty()判断空容器
2. 算法函数：
   • sort()：排序函数，sort(nums.begin(), nums.end())
   • max(a, b)/min(a, b)：取最大 / 最小值，需包含<algorithm>头文件
3. 边界处理：
   • 空数组或长度不足的情况（如if (nums.size() < 3) return ...）
   • 指针越界问题（双指针中left < right的条件判断）

283.移动零

第一种是双指针方法（先放置非零元素再填充0），设置快慢指针，慢指针用来指示非零元素所在位置，快指针用来遍历数组。两个指针都从头开始，其实慢指针一直都指着当前最靠前的0元素，当快指针所指的元素非零时，将非零元素赋值在当前0元素所在的位置，以此类推。这样子等遍历结束之后，slow指针就指向的是非零元素的最后，从slow指针之后的所有元素都赋值为0即可。

class Solution {

public:

    void moveZeroes(vector<int>& nums) {

        //慢指针用来记录非零元素应该存放的位置

        int slow = 0;

        //快指针用来遍历数组

        for(int fast = 0; fast < nums.size(); fast++){

            //如果一个元素不等于0就把他放到当前慢指针的位置

            if(nums[fast] != 0){

                nums[slow] = nums[fast];

                slow++;

            }

            //如果是0则什么都不做，快指针继续向前遍历

        }

        //此时所有非零元素已经按顺序转移到了数组前面

        //从慢指针的位置开始剩下位置都填充为0

        //此时慢指针的位置之前都是非零元素，后边都是0

        for(int i = slow; i < nums.size(); i++){

            nums[i] = 0;

        }

    }

};

第二种部分是交换法，其实也算是双指针法吧只是思路不同。i指针找零元素，j指针找非零元素。当找到i位置是0的时候，j往后遍历到首个非零元素，两者交换直到遍历整个数组。

class Solution {

public:

    void moveZeroes(vector<int>& nums) {

        //指针i寻找0元素

        int i = 0;

        int n = nums.size();

        //指针j寻找非零元素

        for(int j = 0; j < n; j++){

            if(nums[j] != 0){

                //当前i位置是零元素，避免自己和自己交换

                if(i != j){

                    swap(nums[i], nums[j]);

                }

                i++;

            }

        }

    }

};

11．乘最多水的容器

第一个方法是双指针法。水（矩形）面积取决于两个边的长度和两个边之间的宽，双指针往中间移动，宽度一定减小，为了尽可能让面积变大，只能让短边移动才有可能使面积变大。

class Solution {

public:

    int maxArea(vector<int>& height) {

        int left = 0;

        int right = height.size() - 1;

        int max_area = 0;

        while(left < right){

            //计算当前的长宽和面积

            int width = right - left;

            int current_height = min(height[left], height[right]);

            int current_area = width * current_height;

            max_area = max(max_area, current_area);

            //移动较短的线段，才有可能找到最大的面积，因为最大面积取决于线段中间的宽度还有线段的高度，指针移动的过程中线段之间的宽度一定减小，所以为了让形成的矩形面积更大，只能让短线段变长，才有可能面积会增大。

            if(height[left] < height[right]){

                left++;

            }

            else{

                right--;

            }

        }

        return max_area;

    }

};

第二种方法是暴力枚举不推荐

class Solution {

public:

    int maxArea(vector<int>& height) {

        int n = height.size(); // 获取数组长度

        int max_area = 0;      // 记录最大面积

       

        // 外层循环：枚举左边界（第一条线段）

        for (int i = 0; i < n; ++i) {

            // 内层循环：枚举右边界（第二条线段，必须在左边界右边）

            for (int j = i + 1; j < n; ++j) {

                // 计算宽度：右边界索引 - 左边界索引

                int width = j - i;

               

                // 高度由较短的线段决定

                int current_height = min(height[i], height[j]);

               

                // 计算当前面积并更新最大值

                int current_area = width * current_height;

                max_area = max(max_area, current_area);

            }

        }

       

        return max_area;

    }

};

15.三数之和

有点像两数之和的进阶版，其实还是固定一个数然后用两数之和的方法。注意考虑答案重复的问题，所以在得到一组解的时候，要把指针移动到与解的值不同的元素的位置上。

class Solution {

public:

    vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> result;

        int n = nums.size();

        //排序

        sort(nums.begin(), nums.end());

        for(int i = 0; i < n; i++){

            //跳过相同元素

            if(i > 0 && nums[i] == nums[i - 1]){

                continue;

            }

            //在i之后的部分设置双指针

            int left = i + 1;

            int right = n - 1;

            //x+y+nums[i]=0   固定nums[i]则x+y = -nums[i]

            int target = -nums[i];

            while(left < right){

                int current_sum = nums[left] + nums[right];

                if(current_sum == target){

                    result.push_back({nums[i], nums[left], nums[right]});

                    //去重，跳过相同元素

                    while(left < right && nums[left] == nums[left + 1]){

                        left++;

                    }

                    //去重，跳过双重元素

                    while(left < right && nums[right] == nums[right - 1]){

                        right--;

                    }

                    //开始找下一对

                    left++;

                    right--;

                }

                //当前和小于目标值，需要增大和，左指针右移

                else if(current_sum < target){

                    left++;

                }

                //当前和大于目标值，需要减小和，右指针左移

                else{

                    right--;

                }

            }

        }

        return result;

    }

};

42.接雨水（困难）

只学一个双指针吧。设置双指针，遍历整个池子，计算每个位置当前可以盛多少水，把这个位置能盛的水的数量加到water里，以此类推。

class Solution {

public:

    int trap(vector<int>& height) {

        if(height.size() < 3) return 0;

        int left = 0;

        int right = height.size() - 1;

        int left_max = 0;  // 左侧已遍历元素中的最大高度

        int right_max = 0; // 右侧已遍历元素中的最大高度

        int water = 0;     // 接住的雨水总量

        while(left < right){

            // 左侧高度较低，移动左指针

            if(height[left] < height[right]){

                // 更新左侧最大高度

                if(height[left] >= left_max){

                    left_max = height[left];

                }

                else{

                    // 当前位置能接住的雨水 = 左侧最大高度 - 当前高度

                    water += left_max - height[left];

                }

                left++;

            }

            // 右侧高度较低或相等，移动右指针

            else{

                // 更新右侧最大高度

                if(height[right] >= right_max){

                    right_max = height[right];

                }

                else{

                    // 当前位置能接住的雨水 = 右侧最大高度 - 当前高度

                    water += right_max - height[right];

                }

                right--;

            }

        }

        return water;

    }

};

三、滑动窗口

核心解题思维总结

1. 无重复字符的最长子串：寻找字符串中最长的不包含重复字符的连续子串
   • 核心思路：使用可变大小的滑动窗口，右指针扩展窗口，左指针在遇到重复字符时收缩窗口，通过哈希表记录字符最后出现的位置以快速调整左边界
   • 思维拓展：窗口的 "伸缩性" 是应对 "最长 / 最短子串" 问题的关键，通过动态调整边界找到最优解
2. 找到字符串中所有字母异位词：在长字符串中寻找与短字符串为字母异位词的所有子串
   • 核心思路：使用固定大小的滑动窗口（窗口大小等于短字符串长度），通过比较字符计数判断是否匹配，滑动时仅更新边界字符的计数
   • 思维拓展：当需要寻找 "长度固定且满足特定条件" 的子串时，固定窗口大小能简化问题

滑动窗口技术的两类应用

滑动窗口的核心是通过维护一个 "窗口" 范围（由左右指针界定）来减少重复计算，根据窗口大小是否固定可分为两类：

1. 可变大小窗口（如无重复字符的最长子串）：
   • 适用场景：寻找最长 / 最短满足条件的子串（长度不固定）
   • 操作方式：
     • 右指针主动扩展窗口（通常从左到右遍历）
     • 左指针被动收缩窗口（当窗口不满足条件时）
     • 动态更新窗口的最优解（如最长长度）
   • 关键：如何判断窗口是否满足条件（如是否包含重复字符）
2. 固定大小窗口（如字母异位词查找）：
   • 适用场景：寻找长度固定且满足条件的子串（如与目标串长度相同的字母异位词）
   • 操作方式：
     • 窗口大小固定为目标长度
     • 整体滑动窗口（每次移动一步，移除左边界字符，添加右边界新字符）
     • 每次滑动后检查窗口是否满足条件
   • 关键：高效更新窗口状态（如字符计数）

窗口状态的维护方法

为了判断窗口是否满足条件，需要高效维护窗口状态，常用两种方法：

1. 哈希表（unordered_map）：
   • 适用场景：字符集不确定（如包含大小写字母、数字、符号等）
   • 存储内容：键为字符，值为该字符在窗口中的出现次数
   • 优点：通用性强，适用于任意字符
   • 注意点：当字符计数变为 0 时，最好从哈希表中删除该键，避免比较错误
2. 数组：
   • 适用场景：字符集范围已知且有限（如仅包含小写字母 26 个）
   • 存储内容：用索引映射字符（如c - 'a'映射到 0-25），值为出现次数
   • 优点：访问速度比哈希表快，空间占用固定且更小
   • 示例：vector<int> count(26, 0)用于存储小写字母计数

C++ 实现中的关键操作

1. 窗口边界计算：
   • 可变窗口长度：right - left + 1（用于更新最长长度）
   • 固定窗口起始索引：i - p_len + 1（i为当前右边界，p_len为窗口大小）
2. 字符计数更新：
   • 添加字符：count[c]++
   • 移除字符：count[c]--（固定窗口滑动时）
   • 哈希表需处理计数为 0 的情况：if (count[c] == 0) count.erase(c)
3. 条件判断：
   • 重复字符检查：hash_map.find(c) != hash_map.end() && hash_map[c] >= left
   • 字符计数匹配：window_count == target_count（数组或哈希表直接比较）

3.无重复字符的最长子串

第一个方法是滑动窗口+哈希表，哈希表存某个字符出现的最后位置。设置两个指针分别代表左右两个边界，当检测到有一个字符之前已经出现过，那么就意味着这个字符上一次出现的位置一定是左边界，因为我们规定如果遇见了已经出现的字符就要立刻右移左边界。

class Solution {

public:

    int lengthOfLongestSubstring(string s) {

        unordered_map<char,int> char_index;

        int max_length = 0;

        int left = 0;

        // 遍历字符串，right作为滑动窗口的右边界

        for(int right = 0; right < s.size(); right++){

            char current_char = s[right];

           

            // 如果当前字符已经在哈希表中，且其索引在左边界右侧

            // 说明出现重复，需要移动左边界到重复字符的下一个位置

            if(char_index.find(current_char) != char_index.end() && char_index[current_char] >= left){

                left = char_index[current_char] + 1;

            }

            // 更新当前字符的最后出现位置为右边界

            char_index[current_char] = right;

            // 计算当前窗口长度（右边界-左边界+1），并更新最大长度

            max_length = max(max_length, right - left + 1);

        }

        return max_length;

    }

};

438.找到字符串中所有字母异位词

第一种方法是滑动窗口+哈希表。这个方法就是使用哈希表维护所求子串p和窗口内每个字符出现情况，滑动窗口的过程中去掉前边的字符，加上后边的字符，每次都更新一下窗口内的字符出现情况。通过比较子串p和窗口内的字符出现情况来判断是否为字母异位词

class Solution {

public:

    vector<int> findAnagrams(string s, string p) {

        vector<int> result;

        int s_len = s.size();

        int p_len = p.size();

        // 边界情况：如果s长度小于p，直接返回空结果

        if(s_len < p_len) return result;

        // 哈希表存储p中每个字符的出现次数

        unordered_map<char,int> p_count;

        // 哈希表存储当前窗口中每个字符的出现次数

        unordered_map<char,int> window_count;

        // 初始化p的字符计数

        for(char c : p){

            p_count[c]++;

        }

        // 初始化第一个窗口（前p_len个字符）的计数

        for(int i = 0; i < p_len; i++){

            window_count[s[i]]++;

        }

        // 检查第一个窗口是否是字母异位词

        if(p_count == window_count){

            result.push_back(0);

        }

        for(int i = p_len; i < s_len; i++){

            // 移除窗口左侧的字符（即将移出窗口的字符）

            char left_char = s[i - p_len];

            window_count[left_char]--;

            // 如果计数变为0，从哈希表中删除该键（避免比较时出现问题）

            if(window_count[left_char] == 0){

                window_count.erase(left_char);

            }

            // 添加新进入窗口的右侧字符

            char right_char = s[i];

            window_count[right_char]++;

            // 比较当前窗口与p的字符计数是否一致

            if(window_count == p_count){

                result.push_back(i - p_len + 1);

            }

        }

        return result;

    }

};

另外一种思路是用滑动窗口+数组，思路和第一种方法大致相同，只是说使用26个字母的索引来存储相应的数据。

class Solution {

public:

    vector<int> findAnagrams(string s, string p) {

        vector<int> result;

        int s_len = s.size();

        int p_len = p.size();

        // 边界情况处理

        if(s_len < p_len) return result;

        // 用数组记录字符出现次数（仅适用于小写字母）

        // index 0-25对应字母a-z

        vector<int> p_count(26, 0);

        vector<int> window_count(26, 0);

        for(char c : p){

            p_count[c - 'a']++; // 'a'对应0，'b'对应1，以此类推

        }

        for(int i = 0; i < p_len; i++){

            window_count[s[i] - 'a']++;

        }

        if(p_count == window_count){

            result.push_back(0);

        }

        for(int i = p_len; i < s_len; i++){

            // 移除左侧即将离开窗口的字符

            window_count[s[i - p_len] - 'a']--;

            // 添加右侧新进入窗口的字符

            window_count[s[i] - 'a']++;

            if(window_count == p_count){

                result.push_back(i - p_len + 1);

            }

        }

        return result;

    }

};     

四、子串

560.和为k的子数组

最笨的方法就是暴力枚举，但是最好的办法是使用前缀和+哈希表，遍历数组的同时记录前i个元素的前缀和，target值k等于连续的几个元素的和，索引j到i的子数组和可以转变为prefix[i]-prefix[j-1]，寻找子数组和为 K，即寻找 prefix[i] - prefix[j-1] = K，等价于 prefix[j-1] = prefix[i] - K。当计算到当前前缀和prefix[i]时，通过查找 prefix[i] - k的出现次数，可直接得到以 i 为结尾的符合条件的子数组个数。

class Solution {

public:

    int subarraySum(vector<int>& nums, int k) {

        //键是前缀和，值是该前缀和出现的次数

        unordered_map<int, int> prefix_count;

        //初始化：前缀和为0的情况出现1次（用于处理子数组从索引0开始的情况）

        prefix_count[0] = 1;

        //当前前缀和（从索引0代当前索引的和）

        int current_prefix = 0;

       

        int result = 0;

        //遍历数组，计算前缀和并查找符合条件的子数组

        for(int num: nums){

            //更新当前前缀和

            current_prefix += num;

            //目标前缀和：如果存在前缀和为currentprefix - k

            //说明这两个前缀和之间的子数组为x

            int target = current_prefix - k;

            //如果目标前缀和存在于哈希表中，累计其出现次数

            if(prefix_count.find(target) != prefix_count.end()){

                result += prefix_count[target];

            }

            //将当前前缀和加入哈希表（次数加1）

            prefix_count[current_prefix]++;

        }

        return result;

    }

};

附上暴力枚举代码

class Solution {

public:

    int subarraySum(vector<int>& nums, int k) {

        int count = 0; // 记录满足条件的子数组个数

        int n = nums.size();

       

        // 外层循环：枚举子数组的起始索引

        for (int i = 0; i < n; ++i) {

            int current_sum = 0; // 记录从i开始的子数组的和

           

            // 内层循环：枚举子数组的结束索引（从i到n-1）

            for (int j = i; j < n; ++j) {

                current_sum += nums[j]; // 累加元素，计算子数组和

               

                // 如果当前子数组和等于k，计数+1

                if (current_sum == k) {

                    count++;

                }

            }

        }

       

        return count;

    }

};

239.滑动窗口最大值

最简单的方法就是枚举，每次都遍历窗口内的数字找到最大的推入result向量里，但是这样子会很麻烦，附上枚举代码

class Solution {

public:

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> result;

        int n = nums.size();

        for(int i = 0; i <= n - k; i++){

            int current_max = nums[i];

            for(int j = i; j < i + k; j++){

                current_max = max(current_max, nums[j]);

            }

            result.push_back(current_max);

        }

        return result;

    }

};

但实际上，每次移动的话，里边的k-1个元素其实是不动的，只是队列头的元素去掉，队列尾新加一个，所以我们其实可以判断一下走的元素和进的元素和窗口内最大值的大小即可。

我们创建一个队列dq，让数组的索引作为元素，这样子保证这个队列是严格递减的，进来一个数跟当前队列的值作比较，如果没有新进来的数大，那就直接把这个数pop出去，因为这个数以后也不可能是最大值。

class Solution {

public:

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> result;

        //是一个单调队列，存储元素的索引，这样子能保证队列内的元素的数值严格递减

        deque<int> dq;

        int n = nums.size();

        for(int i = 0; i < n; i++){

            //移除队列中超出窗口的元素（左边界）

            //即队头元素的索引小于左边界

            if(!dq.empty() && dq.front() < i - k + 1){

                dq.pop_front();

            }

            //移除队列中所有小于当前元素的元素，因为他们不可能成为后续窗口的最大值

            while(!dq.empty() && nums[i] >= nums[dq.back()]){

                dq.pop_back();

            }

            //将当前元素索引加入队列

            dq.push_back(i);

            //当窗口完全形成i>=k-1的时候，窗口才算完全包含k个元素，此时队头元素就是当前窗口的最大值

            if(i >= k - 1){

                result.push_back(nums[dq.front()]);

            }

        }

        return result;

    }

};

76.最小覆盖子串

使用滑动窗口在s中寻找包含t所有字符的最小窗口，通过哈希表记录字符需求和当前窗口的字符计数，动态调整窗口大小。用INT_MAX初始化最小长度，最终若仍为INT_MAX说明无有效子串。

扩展阶段右指针右移，将字符加入窗口，直到窗口包含t的所有字符

收缩阶段左指针右移，尝试缩小窗口，直到窗口不再满足条件，过程中记录最小窗口最终得到的最小窗口就是答案

class Solution {

public:

    string minWindow(string s, string t) {

        //创两个哈希表保存t每个字符的需求量和当前窗口中每个字符的数量

        unordered_map<char, int> need;

        unordered_map<char, int> window;

        //构建need哈希表

        for(char c: t){

            need[c]++;

        }

        //声明滑动窗口的左右边界、当前拆囊个口中满足需求的字符种类数

        //最小覆盖子串的起始索引、最小覆盖子串长度

        int left = 0, right = 0;

        int valid = 0;

        int start = 0;

        int len = INT_MAX;

        //扩展右边界

        while(right < s.size()){

            //新加的字符

            char c = s[right];

            //右边界右移

            right++;

            //如果t需要字符c

            if(need.count(c)){

                //更新窗口计数

                window[c]++;

                //若达到了need的需求，valid增加

                if(window[c] == need[c]){

                    valid++;

                }

            }

            //当所有字符都满足了t的需求时候，尝试右移左边界

            while(valid == need.size()){

                //更新当前满足的最小覆盖子串

                if(right - left < len){

                    start = left;

                    len = right - left;

                }

                //现在开始尝试能不能把这个最小子串缩小一些

                //d为即将移除的字符

                char d = s[left];

                left++;

                //如果d是t需要的字符

                if(need.count(d)){

                    //如果此时窗口内部的字符已经满足t，但是现在需要去掉一个字符

                    if(window[d] == need[d]){

                        //满足字符种类数减1

                        valid--;

                    }

                    //窗口现在有的字符d个数减1

                    window[d]--;

                }

            }

        }

        //三元运算

        return len == INT_MAX ? "" : s.substr(start, len);

    }

};

五、普通数组

53.最大子数组和

设计动态规划，维护两个值，分别是当前最大值和全局最大值，从局部最优解推出全局最优解。遍历数组，每次都对比当前元素和当前元素+子数组的和的大小。

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        if(nums.empty()) return 0;

        int current_max = nums[0];

        int global_max = nums[0];

        for(int i = 1; i < nums.size(); i++){

            //要么将当前的元素加入前一个子数组，要么重新开始一个子数组

            //选择两者最大的那个作为新的currentmax

            current_max = max(nums[i], current_max + nums[i]);

            //更新全局最大和

            global_max = max(global_max, current_max);

        }

        return global_max;

    }

};

56.合并区间

将这些区间按照左边界排序，这样子的话相邻的区间就会被排序到一起，方便合并。然后创建一个result向量，将第一个interval放进去，从第二个区间开始遍历，每次都判断当前区间是否和结果最后一个区间重叠（即当前区间的左边界<=最后一个结果区间的右边界），若重叠则更新结果区间，否则直接把当前区间加入结果区间里边。

class Solution {

public:

    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        vector<vector<int>> result;

        if(intervals.empty()) return result;

        //按intervals的第一个元素排序，重叠区间会相邻

        sort(intervals.begin(), intervals.end());

        //初始化结果数组，把第一个区间放进去

        result.push_back(intervals[0]);

        for(int i = 1; i < intervals.size(); i++){

            //当前区间的起始和结束

            int current_start = intervals[i][0];

            int current_end = intervals[i][1];

            //结果数组中最后一个已经合并区间的起始和结束

            int last_start = result.back()[0];

            int last_end = result.back()[1];

            //判断当前区间是否与最后一个已合并区间重叠

            if(current_start <= last_end){

                //重叠的话更新区间边界

                result.back()[1] = max(last_end, current_end);

            }

            else{

                //不重叠就直接将当前区间加入结果数组

                result.push_back(intervals[i]);

            }

        }

        return result;

    }

};

189.轮转数组

第一种方法是三次轮转，结果相当于循环移动

class Solution {

public:

    void rotate(vector<int>& nums, int k) {

        int n = nums.size();

        if(n == 0 || k == 0) return;

        //k>=n的时候相当于轮转k%n次

        k = k % n;

        //翻转整个数组

        reverse(nums, 0 , n - 1);

        //翻转前k个

        reverse(nums, 0 , k - 1);

        //翻转剩下n-k个

        reverse(nums, k , n - 1);

    }

private:

    //创建辅助函数

    void reverse(vector<int>& nums, int start, int end){

        while(start < end){

            //从两头开始往中间移动指针

            swap(nums[start], nums[end]);

            start++;

            end--;

        }

    }

};

第二种方法是使用一个临时数组，遍历原数组将数组放在临时数组中移动之后的位置，最后将原数组等于临时数组

class Solution {

public:

    void rotate(vector<int>& nums, int k) {

        int n = nums.size();

        if (n == 0 || k == 0) return;

        k = k % n;

       

        // 创建额外数组存储轮转后的结果

        vector<int> temp(n);

       

        // 遍历原数组，计算每个元素在新数组中的位置

        for (int i = 0; i < n; ++i) {

            // 轮转后，元素nums[i]的新位置为(i + k) % n

            // 例如：i=4, k=3, n=7 → (4+3)%7=0 → nums[4]移到temp[0]

            temp[(i + k) % n] = nums[i];

        }

       

        // 将新数组的结果复制回原数组

        nums = temp;

    }

};

238.除自身以外数组的乘积

结果数组本身要返回的，可以先把 left 数组的内容存在结果数组里，这样就省了一个 left 数组。那 right 数组呢？其实不用专门存，用一个变量动态记录就行。步骤大概是先遍历一遍算左侧乘积，存在 res 里。然后从右往左遍历，用一个变量 right 记录当前的右侧乘积（刚开始是 1，因为最右边元素右侧没东西），每次把 res [i]（也就是左侧乘积）乘以 right，就是当前位置的结果。然后再更新 right，把当前元素乘进去（因为下一个左边的元素，它的右侧乘积要包含当前元素）。

class Solution {

public:

    vector<int> productExceptSelf(vector<int>& nums) {

        int n = nums.size();

        vector<int> res(n, 1);  //存做前缀，再存最终结果

        int right = 1;  //动态记录右前缀乘积

        for(int i = 1; i < n; i++){

            //计算左前缀

            res[i] = res[i-1] * nums[i-1];

        }

        for(int i = n - 1; i >= 0; i--){

            res[i] *= right;   //计算左前缀*右前缀

            right *= nums[i];   //更新右前缀（包括当前元素，供左侧元素使用

        }

        return res;

    }

};

41.缺失的第一个正数

这题要找未出现的最小正整数，比如 [1,2,0] 里最小的是 3，[-1,3,4] 里最小的是 1。首先想到，最小的正整数肯定在 1 到 n+1 之间（n 是数组长度），因为如果 1 到 n 都出现了，答案就是 n+1。

那怎么快速判断 1 到 n 之间哪些数没出现呢？可以用哈希表啊先把数组里的数存进哈希表，然后从 1 开始逐个检查，第一个不在哈希表里的就是答案。不过要注意，数组里可能有负数或者大于 n 的数，这些可以直接忽略，因为它们不影响 1 到 n 之间的判断。

比如数组 [3,4,-1,1]，n=4。哈希表里有 3,4,-1,1。检查 1：在；检查 2：不在，所以答案是 2。这种方法简单直接，就是需要额外的哈希表空间。

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

        unordered_set<int> num_set;

        int n = nums.size();

        for(int i = 0; i < n; i++){

            num_set.insert(nums[i]);

        }

        for(int i = 1; i <= n + 1; i++){

            if(num_set.find(i) == num_set.end()){

                return i;

            }

        }

        return n + 1;

    }

};

上面的方法用了额外空间，题目其实希望用 O (1) 空间。怎么在原地做呢？可以利用数组本身当哈希表！核心想法是：让数值为 i 的数放在索引 i-1 的位置（比如 1 放在 0 号索引，2 放在 1 号索引），这样最后遍历数组时，第一个索引 i 对应的数不是 i+1 的，就是答案。

步骤大概是：

先把数组里的负数、0 和大于 n 的数都改成 n+1（这些数不影响结果，且方便后续处理）。

遍历数组，对每个数 x（此时 x 肯定是正数），如果 x <=n，就把索引 x-1 的位置标记为负数（表示 x 这个数存在）。

最后遍历数组，第一个正数对应的索引 + 1 就是答案；如果全是负数，答案就是 n+1。

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

        int n = nums.size();

        //把无效数字改成n+1

        for(int i = 0; i < n; i++){

            if(nums[i] <= 0 || nums[i] > n){

                nums[i] = n + 1;

            }

        }

        //标记存在的数字（用负数标记）

        for(int i = 0; i < n; i++){

            int x = abs(nums[i]); //取绝对值，因为可能已经被标记为负数

            if(x <= n){

                //把索引x-1的位置标记为负数，表示x存在

                nums[x - 1] = -abs(nums[x - 1]);

            }

        }

        //找第一个整数，其索引+1就是答案

        for(int i = 0; i < n; i++){

            if(nums[i] > 0){

                return i + 1;

            }

        }

        return n + 1;

    }

};