LeetCode子串问题经典题目解析

560. 和为k的子数组

解题思路

  • 使用前缀和 + 哈希表优化
  • 子数组和可以表示为两个前缀和之差
  • 一边计算前缀和一边记录到哈希表
  • 查找是否存在 presum-k 的 前缀和

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        map<int,int> mp;
        mp[0]=1;  //处理空数组的情况
        int r=0;
        int presum=0;
        for(int i = 0;i<nums.size();i++) {
            presum +=nums[i];
            r+=mp[presum-k];
            mp[presum]++;
        }
        return r;
    }
};

239. 滑动窗口最大值

解题思路

  • 使用哈希表记录元素出现次数
  • 使用最大堆维护当前窗口最大值
  • 移动窗口时：
    1. 新元素加入堆和哈希表
    2. 删除元素从哈希表移除
    3. 堆顶元素不在哈希表中时弹出

代码实现

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
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        auto cmp = [](int left, int right) { return left < right; };
        priority_queue<int, vector<int>, decltype(cmp)> maxHeap(cmp);
        unordered_map<int,int> count;
        vector<int> result;
        
        // 初始化窗口
        for(int i = 0; i < k; i++) {
            maxHeap.push(nums[i]);
            count[nums[i]]++;
        }
        result.push_back(maxHeap.top());
        
        // 滑动窗口
        for(int i = k; i < nums.size(); i++) {
            count[nums[i-k]]--;
            count[nums[i]]++;
            maxHeap.push(nums[i]);
            
            // 移除堆顶无效元素
            while(!count[maxHeap.top()]) {
                maxHeap.pop();
            }
            result.push_back(maxHeap.top());
        }
        return result;
    }
};

76. 最小覆盖子串

解题思路

  • 使用两个哈希表：
    1. 记录目标字符串中字符出现次数
    2. 记录当前窗口中字符出现次数
  • 使用滑动窗口：
    1. 右指针扩展直到包含所有目标字符
    2. 左指针收缩优化长度
    3. 维护最小覆盖子串

代码实现

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
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for(char c : t) need[c]++;
        
        int left = 0, right = 0;
        int valid = 0;
        int start = 0, len = INT_MAX;
        
        while(right < s.size()) {
            char c = s[right];
            right++;
            if(need.count(c)) {
                window[c]++;
                if(window[c] == need[c]) valid++;
            }
            
            while(valid == need.size()) {
                if(right - left < len) {
                    start = left;
                    len = right - left;
                }
                
                char d = s[left];
                left++;
                if(need.count(d)) {
                    if(window[d] == need[d]) valid--;
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

总结

子串问题的核心技巧：

  1. 前缀和 + 哈希表优化
  2. 滑动窗口 + 数据结构维护
  3. 双指针 + 状态记录

常见优化方向：

  • 空间换时间
  • 合理使用数据结构
  • 双指针减少遍历次数