数据结构（hot 100）

两数之和

题目描述

​ 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

思路：

具体思路：

首先使用unordered_map，在遍历原数组时，边查边找。

如果没找到，就把当前值的值和下标存入unordered_map，以便下次寻找可以搜素以前的键值对，看是否有满足情况（target-nums[i]）的key,若有，取出对应的value(iter->second)和当前的数组下标一起返回。当然最坏的情况，遍历完了，也没有符合情况的出现。可以直接返回空。

std::unordered_map的核心特性：

1. 基于哈希表实现（Hash Table）

  • unordered_map 通过哈希函数（std::hash）将键（key）映射到一个桶（bucket）中，实现常数时间复杂度（O(1)）的查找、插入和删除操作（平均情况）。
  • 哈希冲突通过链表（或更优化的结构）解决。
  1. 键唯一（Key is Unique）
  • 每个键（key）在 unordered_map 中必须是唯一的，如果插入相同键，会覆盖原有值或插入失败（取决于操作方式）。

3. 无序（Unordered）

  • 元素的存储顺序不保证稳定性或有序性，与插入顺序无关。
  • 如果需要有序容器，应使用 std::map。

4. 自动扩容

  • unordered_map 会根据负载因子（load factor）自动扩展桶的数量，以保持操作效率。
  • 用户可以手动调整负载因子和桶数量（如 rehash() 或 reserve() 函数）。

5. 允许自定义哈希函数与相等比较器

  • 支持用户为自定义类型指定哈希函数（通过模板参数 Hash 和 KeyEqual）。
1
2
3
4
5
cpp


复制编辑
std::unordered_map<MyType, int, MyHash, MyEqual>

6. 快速访问接口

  • operator[]：快速访问键对应的值，如果键不存在，则自动插入默认值。
  • find()：返回一个迭代器，指向查找到的键值对，否则为 end()。

7. 不支持排序算法

  • 由于无序存储，标准排序算法（如 sort）不能直接应用于 unordered_map，但可以通过将其内容复制到 vector<pair<>> 后排序实现。

8. 多线程下非线程安全

  • 多线程环境下访问 unordered_map 必须加锁或使用线程安全容器。

代码块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int,int> map;
        for(int i=0;i<nums.size();i++){
            auto iter =map.find(target-nums[i]);
            if(iter!=map.end()){
                return {i,iter->second};
            }
            map.insert(pair<int,int>(nums[i],i));
        }
        return {};
    }
};

时间复杂度：

  • 一次遍历 nums 数组，时间是 O(n)。
  • 对于每个元素：
    • map.find(...) 查找操作的平均时间复杂度是 **O(1)**。
    • map.insert(...) 插入操作的平均时间复杂度也是 **O(1)**。

因此，总体时间复杂度是：

**O(n)**（n 是数组中元素的数量）

空间复杂度：

  • 最多会向 unordered_map 中插入 n 个元素（每个 nums[i] 和其索引 i）。
  • 所以空间复杂度与 nums 的大小成正比。

**O(n)**（额外使用了哈希表来存储 n 个键值对）

字母异位词分组

题目描述：

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

1
2
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1
2
输入: strs = [""]
输出: [[""]]

示例 3:

1
2
输入: strs = ["a"]
输出: [["a"]]

提示：

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

思路

具体思路：

​ 首先使用std::unordered_map结构，当然不用再介绍了。这个题的意思是把那些排序之后相同的单词放在一个组合。

所以我们可以先使用unordered_map<string,vector>存储键值对，键就是排序之后的单词，毕竟排序之后都一样。

键对应的值就是对应的单词（排序相同的单词），最后再遍历这个unordered_map，输出结果。

代码块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        //做这道题首先对于字母异位词 排序之后是相同的，所以可以用一个哈希表，键存储排序后的结果，值为结果集
        std::unordered_map<string,vector<string>> record;
        for(int i=0;i<strs.size();i++){
            string temp=strs[i];
            sort(temp.begin(),temp.end());
            record[temp].emplace_back(strs[i]);

        }
        vector<vector<string>> ans;
        for(auto it=record.begin();it!=record.end();it++){
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

时间复杂度：

假设：

  • n 是字符串数组 strs 的长度。
  • k 是每个字符串的平均长度。
  1. 遍历 strs 中的每个字符串，共 n 次。
  2. 对每个字符串排序：O(k log k)
  3. 哈希表插入/查找键值对：O(1) 平均时间。

所以总时间复杂度为：

O(n * k log k)

空间复杂度：

  • 哈希表 record 最多存 n 个键，每个键存一个 vector<string>，整体字符串内容不变，只是重新组织。
  • 排序后的中间变量 temp 的开销为 O(k)，共用一次。
  • 最终结果 ans 存储所有原字符串内容。

所以额外空间主要包括：

  1. 哈希表键（排序后的字符串）：最多 n 个，每个长度为 k：O(n * k)
  2. 哈希表值（字符串集合）：整体还是输入的字符串，只是重新组织，不算重复存储
  3. 排序的临时变量（重复使用）：忽略不计

因此总空间复杂度为：

O(n * k)

最长连续序列

题目描述：

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

1
2
输入：nums = [1,0,1,2]
输出：3

思路：

具体思路：

​ 首先将数组存入unordered_set中避免重复，为什么用unordered_set，因为找元素它是O(1)。

接下来遍历unordered_set，先判断当前元素有没有前一个连续的元素（例子：当前元素为5，查是否有4），有则跳过，没有则进行下一步，并且这个节点是作为开始节点。

然后先保存当前节点的值和连续序列的长度（这个时候为1），然后循环查找连续序列，最后获得连续序列的长度，再和历史最长连续序

列比较，更新历史最长连续序列。遍历完unordered_set，返回历史最长连续序列即可。

std::unordered_set的特性：

std::unordered_set 是 C++ 标准库中提供的 无序集合容器，它内部基于哈希表实现，主要用于快速判断一个元素是否存在，并确保元素唯一。下面是它的详细特性：

1. 元素唯一（Unique Elements）

  • 它是一个 集合（set），不允许重复元素。
  • 插入相同元素将失败，已有的不会被替换。

2. 基于哈希表（Hash Table）

  • 内部使用哈希表存储元素。
  • 插入、查找、删除的**平均时间复杂度是 O(1)**，非常高效。
  • 如果发生大量哈希冲突，最坏情况会退化为 O(n)，但 STL 默认哈希函数表现良好，一般不会发生。

3. 元素无序（Unordered）

  • 和 std::set（基于红黑树，有序）不同，unordered_set 中的元素存储顺序不固定。
  • 遍历时元素的顺序是哈希桶顺序，不可预测。

4. 可自定义哈希函数（支持自定义类型）

  • 可以为自定义类型提供哈希函数和等价比较函数。
1
std::unordered_set<MyType, MyHash, MyEqual>

5. 常用操作和函数

函数 功能
insert(val) 插入元素，若已存在则不插入
erase(val) 删除元素
find(val) 查找元素，返回迭代器
count(val) 判断元素是否存在（返回 0 或 1）
size() 元素个数
empty() 是否为空
clear() 清空所有元素
begin(), end() 返回迭代器（可用于范围遍历）

5.与 std::set 的区别

特性 std::set（有序） std::unordered_set（无序）
底层结构 红黑树（平衡 BST） 哈希表
元素是否有序 是 否
查找/插入效率 O(log n) 平均 O(1)
内存使用 较少 较多（需额外存哈希结构）
自定义排序 支持 不支持

代码块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        //使用unordered_set存储nums的所有值
        for(const int &num:nums){
            num_set.insert(num);
        }
        int longSum=0;
        for(const int &num:num_set){
            //上述遍历用nums和num_set有什么区别，在leetcode一个能过一个不能过
            //以遍历的每个元素为起点，满足才进行下一步操作
            if(!num_set.count(num-1)){
                //满足条件后，存储当前节点的信息
                int currentNum=num;
                int currentSum=1;
                //寻找该节点的最长连续序列
                while(num_set.count(currentNum+1)){
                    currentNum=currentNum+1;
                    currentSum+=1;
                }
                //最后与longSum比较，更新历史最长连续序列
                longSum=max(currentSum,longSum);
            }
        }
        return longSum;
    }
};

编写代码产生的问题：

上述遍历用nums和num_set有什么区别，在leetcode一个能过一个不能过

遍历 num_set：

  • 每个元素最多只被作为“起点”处理一次。
  • 例如：对于序列 [100, 101, 102, 103]，只有 100 会进入 while 循环处理。
  • 其他如 101、102 在 if (!num_set.count(num - 1)) 时会被跳过（因为 100 已经处理了它们）。
  • 所以是 O(n) 时间复杂度。

遍历 nums：

  • nums 可能包含重复值，也可能无序。
  • 比如你在 nums 中遇到 102，它不是起点，但你仍会试图查找连续数字，造成重复计算。
  • 重复调用 count()，浪费性能，导致 超时 或 错误结果（重复统计）。

时间复杂度：

设输入数组 nums 的长度为 n。

  1. unordered_set 插入 n 个元素：**O(n)**（平均时间，插入是 O(1)）。
  2. 第二个循环遍历 num_set 中的每个元素，每个连续序列只处理一次。
1
if (!num_set.count(num - 1))
  • 这个判断确保每个序列的起点只会被处理一次。
  • 例如序列 [100, 101, 102, 103] 只会从 100 开始处理一次，不会在遍历到 101 时重复处理。

因此：

**总时间复杂度：O(n)**（哈希表操作均为 O(1) 平均时间）

空间复杂度：

  • 使用了一个 unordered_set 存储 n 个整数，占用 O(n) 的空间。
  • 其他变量如 currentNum, currentSum 等为常数空间。

因此：

总空间复杂度：O(n)

移动零

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2
输入: nums = [0]
输出: [0]

思路：

具体思路：

​ 我们可以采用双指针的方法，先left,right同时指向起始点，right到最后位置结束。当right找到非零节点，与left进行值交换，left只有交换结束才left++;这样最后非零节点都在前面，0都在末尾。

代码块：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n=nums.size(),left=0,right=0;
        while(right<n){
            if(nums[right]){
                swap(nums[left],nums[right]);
                left++;
            }
            right++;
        }
    }
};

时间复杂度：

  • right 从 0 遍历到 n-1，每个元素访问一次。
  • 最多发生 n 次 swap 操作（每个非零元素最多被交换一次）。
  • 所以：

总时间复杂度：O(n)

空间复杂度：

  • 只使用了常量级别的辅助变量 left 和 right。
  • 所有操作都在原数组上进行，原地修改，没有开辟额外数组。

总空间复杂度：O(1)

盛最多水的容器

题目描述：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

img

1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

1
2
输入：height = [1,1]
输出：1

思路：

具体思路：

​ 我们采用双指针的方式求解。这个题目的是求解柱子之间的最大面积。我们可以采用将两个指针放在两端，如果左边的柱子高度大于或等于右边的柱子高度，我们先算出容器对应的面积（高度以低柱子为准）。算出后更新历史最大面积。执行完，将右边的柱子向左移动。同时，还有一种情况，左边的柱子高度小于右边的柱子高度，先算出容器对应的面积（高度以低柱子为准）。算出后更新历史最大面积。执行完，将左边的柱子向右移动。直到当前的左柱子和右柱子重合。

代码块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans=0;
        //采用双指针的方式求解
        int left=0;
        int right=height.size()-1;
        while(left<right){
            if(height[left]>=height[right]){
                ans=max(ans,(right-left)*height[right]);
                right--;
            }else{
                ans=max(ans,(right-left)*height[left]);
                left++;
            }
        }
        return ans;
    }
};

时间复杂度：

时间复杂度：O(n)

  • 解释：使用的是双指针方法，从两端向中间遍历整个数组，每一次迭代都会移动左指针或右指针之一，因此总共最多移动 n-1 次。
  • 所以时间复杂度是 **线性的 O(n)**，其中 n 是 height 数组的长度。

空间复杂度：

空间复杂度：O(1)

  • 解释：只使用了常数个额外变量（如 ans, left, right, h, w），不依赖于输入数据的大小。
  • 因此空间复杂度是 **常数级 O(1)**。

三数之和

题目描述：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

思路：

具体思路：

​ 这题的目标是在在整数数组中，找到所有三个数满足和为零，最后结果不可以重复。这个题我们可以先定下一个值，剩下两个值用双指针法遍历，找到符合结果的。还有一些细节，还要考虑不能重复的问题，对于这个问题，我们可以先排序（升序）这个数组，从小到大定第一个值，首先如果这第一个值大于0，这个可以结束了，这个数组就不会存在符合条件的三元组。当然如果当前元素与上一个元素相同，也跳过，这样执行，首先我想的是定第一个元素，当当前元素和下一个元素相同直接跳过，后来发现，[-1,-1,2]这种情况没有考虑。当然那你为甚么还是要写当前元素与上一个元素相同，也跳过，我完全可以不管嘛，那不行，我的思路是当第一个元素是-1时，这一次直接找出所有符合第一个元素是-1的情况，要不然会十分混乱，所以我会说如果当前元素与上一个元素相同，也跳过。因为上一个元素已经找完了第一个元素为-1的三元组了，当避免找完-1还会再出现，我们用了排序。这样第一个元素的逻辑就结束了，接下来找剩下两个，用双指针，左指针指向当前元素的下一个元素，右指针指向末尾元素。我们是要找到所有符合情况，当三元组的值大于0，将右指针左移。当三元组的值小于0，将左指针右移。当三元组的值等于0，将三元组的值加入结果集。接下来再判断找到的左元素是否与后面的元素重复（因为是排序的，相同的元素就在身边）。跳过这些元素，找到的右元素是否与后面的元素重复（因为是排序的，相同的元素就在身边）。跳过这些元素。只要左指针和右指针没有重合，就一直找，找完符合情况的三元组。

代码块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        //先升序排序
        sort(nums.begin(),nums.end());
        //遍历排序后的数组
        for(int i=0;i<nums.size();i++){
            //先定第一个元素
            //第一个元素大于0,因为是升序排序，后面都大于零，那没有满足条件的结果了
            if(nums[i]>0) break;
            //如果上一个元素相同，跳过当前，用下一个
            if(i>0 && nums[i]==nums[i-1]) continue;
            //采用双指针定剩下两个
            int left=i+1;
            int right=nums.size()-1;
            while(left<right){
                if(nums[i]+nums[left]+nums[right]>0) right--;
                else if(nums[i]+nums[left]+nums[right]<0) left++;
                else if(nums[i]+nums[left]+nums[right]==0){
                    ans.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--;
                }
            }

        }
        return ans;
    }
};

时间复杂度：

时间复杂度：O(n^2)

详细分析：

  1. 外层循环遍历数组中的每个数作为固定值 nums[i]，这部分是 O(n)。

  2. 内层使用双指针 left 和 right 来查找另外两个数，最坏情况下每次都需要遍历一次剩余数组，即 O(n)。

  3. 所以总的时间复杂度是：

    O(n^2)

去重操作的影响：

  • 去重操作使用的是 while(left < right && nums[left] == nums[left + 1]) 这类逻辑，在最坏情况下最多也只是跳过相同元素，不改变主导复杂度。

空间复杂度：

空间复杂度：O(1)（不计输出）

解释：

  • 如果不考虑返回结果 ans 所占用的空间（即题目允许将返回值空间复杂度忽略），则使用的额外空间为：
    • 排序使用的可能是原地排序（如 std::sort），**空间复杂度为常数级 O(1)**。
    • 其他仅使用了一些指针和变量，都是常数级空间。
  • 如果 将返回结果的空间也算入，最坏情况是 O(k)，其中 k 是满足条件的三元组个数。

接雨水

题目描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

img

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

思路：

具体思路：

这里采用的是动态规划解法，还有其他方法。动态规划解法，需要构造两个数组分别储存各个节点的左边最大高度和右边最大高度，便于计算当前节点所积水高度。问题在于左边和右边最大高度该如何获取。最左边的左边最大高度就是它自身，最右边的右边最大高度就是它自身，以这两个边界条件，左边最大高度就是当前节点的左边节点的左边最大高度和当前节点的高度的最大值，右边最大高度也是一样。求解出放入之前的两个数组中。已知这两个数组，可以遍历这两个数组，把当前节点的积水量算出，再累加一起，就是所求的雨水量。

代码块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int trap(vector<int>& height) {
        //这题采用动态规划
        int n=height.size();
        if(n==0){
            return 0;
        }
        vector<int> leftMax(n);
        vector<int> rightMax(n);
        leftMax[0]=height[0];
        rightMax[n-1]=height[n-1];

        for(int i=1;i<n;i++){
            leftMax[i]=max(leftMax[i-1],height[i]);
        }
        for(int i=n-2;i>=0;i--){
            rightMax[i]=max(rightMax[i+1],height[i]);
        }
        int ans=0;
        for(int i=0;i<n;i++){
            ans+=min(leftMax[i],rightMax[i])-height[i];
        }
        return ans;
    }
};

时间复杂度：

时间复杂度：O(n)

  • 遍历了三次数组：

    1. 构造 leftMax：O(n)
    2. 构造 rightMax：O(n)
    3. 遍历一次计算总雨水量：O(n)

  • 所以总时间复杂度是：

    O(n)

空间复杂度：

空间复杂度：O(n)

  • 使用了两个辅助数组：
    • leftMax：大小为 n
    • rightMax：大小为 n
  • 所以额外空间是 2n，即 O(n) 空间复杂度。

无重复字符的最长子串

题目描述：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路：

具体思路：

我们使用滑动窗口和哈希表实现这个题目。哈希表存储枚举值的下标，初始值为-1，j值在没有重合的情况下，会在每次循环+1，但是如果遇到重合，j值会跑到对应的下标位置之后的位置（下标位置存储在哈希表中）。只要有重合就调整窗口。

代码块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //滑动窗口和哈希表
        vector<int> pos(128,-1);
        int ans=0;
        //j为滑动窗口的起始节点
        for(int i=0,j=0;i<s.size();i++){
            j=max(j,pos[s[i]]+1);
            ans=max(ans,i-j+1);
            pos[s[i]]=i;
        }
        return ans;
    }
};

时间复杂度：

时间复杂度：O(n)

  • 其中 n 是字符串 s 的长度。
  • 每个字符最多访问两次（一次作为右指针扩展窗口，一次作为左指针缩小窗口）。
  • 所以整体是线性时间复杂度 O(n)。

空间复杂度：

空间复杂度：O(1)

  • 使用了一个 pos 数组来记录 ASCII 字符上次出现的位置，长度是固定的 128（ASCII 字符集）。
  • 即使改成 256（扩展 ASCII）或 100,000（Unicode 范围），只要是定长的字符集，空间复杂度都是 O(1) 常数级。
  • 如果字符集不固定，比如用 unordered_map<char, int>，那空间复杂度是 O(k)，其中 k 是字符集大小。

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

题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

思路：

具体思路：

这道题的整体思路是让我找到对应字符串的所有异位词在一个陌生的字符串里。这里要解决两个问题，首先是异位词问题，找异位词可以通过枚举法，总共26个字母，我们通过数组存储使用字母的个数，最后对比，如果数组相等，就说明是异位词。还有一个问题：在陌生字符串找到所有的异位词，并且返回索引，找异位词是一个范围问题，所以我要使用流动窗口，大小就是对应字符串的大小。在陌生字符串扫描。最后返回结果。

代码块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        //首先记录两字符串的长度
        int sLen=s.size(),pLen=p.size();
        //如果字符串s的长度还不比p字符串长
        if(sLen<pLen){
            return vector<int>();
        }
        //记录结果
        vector<int> ans;
        //记录s字符串和p字符串的字母对应的个数，枚举法
        vector<int> sletter(26);
        vector<int> pletter(26);
        //先试试索引为0的
        for(int i=0;i<pLen;i++){
            ++sletter[s[i]-'a'];
            ++pletter[p[i]-'a'];
        }
        //如果符合，说明索引为0符合情况
        if(sletter==pletter){
            ans.emplace_back(0);
        }
        //之后按照索引为1往后遍历，采取流动窗口,把前一次的流动窗口的第一个去掉，再往后补一个，形成新的流动窗口.
        //注意这里是按流动窗口为整体，上面的循环是为了形成流动窗口。
        for(int i=0;i<sLen-pLen;i++){
            --sletter[s[i]-'a'];
            ++sletter[s[i+pLen]-'a'];

            if(sletter==pletter){
            ans.emplace_back(i+1);
        }
        }
        
        return ans;
    }
};

时间复杂度：

  • 初始化部分：O(p)
  • 滑动窗口：O(n)

由于通常 p 比 n 小，所以总时间复杂度是：O(n)

空间复杂度：

  • 使用了两个长度为 26 的数组：sletter, pletter；
  • 还使用了一个结果数组 ans，最坏情况下长度也是 O(n)；

因此：

空间复杂度是 O(1) + O(k)，其中 k 是结果中异位词的数量，通常最多为 O(n)。

和为 K 的子数组

题目描述：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

1
2
输入：nums = [1,1,1], k = 2
输出：2

示例 2：

1
2
输入：nums = [1,2,3], k = 3
输出：2

思路：

具体思路：

这里采取两个方法，第一种方法就是枚举法，暴力轮询。（为什莫要两种，因为我第一种leetcode超时了）。

方法二：首先通过前缀和这个点，定义 pre[i] 为 [0..i] 里所有数的和，则 pre[i] 可以由 pre[i−1] 递推而来，即：pre[i]=pre[i−1]+nums[i]
那么[j..i] 这个子数组和为 k 这个条件我们可以转化为pre[i]−pre[j−1]==k
简单移项可得符合条件的下标 j 需要满足pre[j−1]==pre[i]−k
所以我们考虑以 i 结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为 pre[i]−k 的 pre[j] 即可。建立以上条件，我们的问题就简化为寻找有多少个符合条件的pre[j]即可，我们建立哈希表，键是前缀和，值是前缀和重复的个数。在遍历的过程中，pre存储当前的前缀和，先不放进哈希表中，先在哈希表中查找是否有键pre-k,有的话，就取出对应的值加到count里，不管找没找到，都要将当前的前缀和存到哈希表中。这代码的逻辑是基于前缀和得出的只要统计有多少个前缀和为 pre[i]−k 的 pre[j] 即可。

代码块：

方法一：枚举法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //这题我们采用枚举法
        int count=0;//返回的结果值
        int n=nums.size();
        for(int start=0;start<n;++start){
            int sum=0;
            for(int end=start;end<n;++end){
                sum+=nums[end];
                if(sum==k){
                    count++;
                }
            }
        }
        return count;
    }
};

方法二：前缀和+哈希表优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //前缀和+哈希表优化
        unordered_map<int,int> mp;
        mp[0]=1;//初始前缀和的个数为1
        int count=0,pre=0;//count是返回结果的，pre是前缀和
        for(auto &temp:nums){
            pre+=temp;
            if(mp.find(pre-k)!=mp.end()){
                count+=mp[pre-k];
            }
            mp[pre]++;
        }
        return count;
    }
};

时间复杂度：

方法一：

时间复杂度：O(n²)

方法二：

O(n) 时间

空间复杂度：

方法一：

空间复杂度：O(1)

方法二：

**O(n)**（最坏情况下所有前缀和都不相同，哈希表大小为 n）