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

题目链接

leetcode

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

/*
    滑动窗口：使用两个指针 left 和 right 来定义滑动窗口的左右边界。
    窗口大小改变。
        当窗口内的字符个数小于 p 的字符个数时，窗口扩张。
        当窗口内的字符个数等于 p 的字符个数时，窗口收缩。
    遍历完成后，返回结果数组。

    时间复杂度：O(n)
        其中 n 是字符串 s 的长度。
        每个字符最多被访问两次。
    空间复杂度：O(1)
       need 和 window 的大小与字符集的大小有关，通常为 O(1)。
       假设字符集为小写字母，大小固定为 26。
*/
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> need, window;
        for (char c : p) {
            need[c]++;
        }

        vector<int> res;
        int left = 0, right = 0;
        int valid = 0;

        while (right < s.size()) {
            char c = s[right];
            right++;
            // 更新窗口内的数据
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) {
                    valid++;
                }
            }

            // 判断左侧窗口是否收缩
            while (right - left >= p.size()) {
                // 窗口符合条件时，将开始索引加入返回结果
                if (valid == need.size()) {
                    res.push_back(left);
                }
                
                char d = s[left];
                left++;
                // 更新窗口内的数据
                if (need.count(d)) {
                    if (window[d] == need[d]) {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }

        return res;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<string> s_cases = { "cbaebabacd", "abab" };
    vector<string> p_cases = { "abc", "ab" };

    for (int i = 0; i < s_cases.size(); i++) {
        vector<int> result = solution.findAnagrams(s_cases[i], p_cases[i]);

        cout << "Input: s = \"" << s_cases[i] 
        << "\", p = \"" << p_cases[i] << "\"" << endl;
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}