yicong@algo: ~/code/03-sliding-window/0438-find-all-anagrams-in-a-string.cpp

yicong@algo:~/code/03-sliding-window$ cat 0438-find-all-anagrams-in-a-string.cpp

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

中等 滑动窗口 题目 ↗ 源码 ↗

// 思路

字母异位词 = 同字母不同排列,长度必须相同。因此问题等价于: 在 s 中找所有长度为 len(p) 的窗口,使其字符频次等于 p 的字符频次。 采用滑动窗口:窗口大小固定为 len(p),right 从左向右滑动, 每次右边进一个字符、左边出一个字符,维护 window 频次表。 用 unordered_map 的 operator== 判断两个 map 是否相等(全等比较 key+value)。

// 时间复杂度

O(|s| * |C|),|C| 为字符集大小(本题 26)

// 空间复杂度

O(|C|)

// 易错点

- right < len(p) 时窗口尚未填满,不要做左边出窗的判断; - window.erase 当且仅当计数归零时才删 key,否则 == 比较时 key 不一致; - unordered_map == 要求两个 map 的 key 集合完全相同; 若 window={a:1} 而 pp={a:1,b:0},两者不相等——erase 是必要的; - 答案下标 = right-len(p)+1(左边界)。

// 面试口述要点

- 先说哈希表 + 固定窗口的朴素做法; - 引出优化:不用 unordered_map== 判断,改用数组 diff 计数器, 当 diff==0 说明窗口和 p 的频次完全一致,时间降到 O(|s|)。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // ================================================================
    // 版本一:unordered_map 滑动窗口(你的写法)
    // 窗口大小固定为 len(p),用 unordered_map== 判断频次相等。
    // 直观,但 unordered_map== 每次要遍历整个字符集,常数较大。
    // ================================================================
    vector<int> findAnagrams(string s, string p) {
        int lp = (int)p.size();
        vector<int> ans;
        unordered_map<char, int> target, window;
        for (char c : p) ++target[c];

        for (int right = 0; right < (int)s.size(); ++right) {
            ++window[s[right]];
            if (right >= lp) {
                char out = s[right - lp];
                if (--window[out] == 0) window.erase(out);
            }
            if (window == target) ans.push_back(right - lp + 1);
        }
        return ans;
    }

    // ================================================================
    // 版本二:数组 + diff 计数器,O(|s|),面试更优写法
    // 核心:用 vector<int> cnt(26, 0) 记录窗口相对于 target 的频次差值。
    //   - cnt[c] > 0:窗口中 c 多了
    //   - cnt[c] < 0:窗口中 c 少了
    //   - cnt[c] == 0:窗口中 c 的数量恰好等于 target
    // 用一个整数 diff 记录"有多少个字符的 cnt 不为零":
    //   right 进窗:--cnt[in](若从 -1 变 0,diff--)
    //   left  出窗:++cnt[out](若从 0 变 1,diff++)
    //   diff == 0 时,所有 cnt 均为 0,窗口与 target 完全匹配。
    // 无需 == 比较,每次 O(1) 更新判断。
    // ================================================================
    vector<int> findAnagrams_v2(string s, string p) {
        int n = (int)s.size(), lp = (int)p.size();
        vector<int> cnt(26, 0);
        for (char c : p) --cnt[c - 'a'];   // target 中有的字符在 cnt 中为负

        vector<int> ans;
        int diff = 0;                      // 有多少个字符的 cnt 不为 0
        for (int i = 0; i < 26; ++i)
            if (cnt[i] != 0) ++diff;

        for (int right = 0; right < n; ++right) {
            char in = s[right] - 'a';
            if (cnt[in] == 0) ++diff;      // 本来是 0,现在要变负了
            --cnt[in];
            if (cnt[in] == 0) --diff;      // 恰好归零

            if (right >= lp) {
                char out = s[right - lp] - 'a';
                if (cnt[out] == 0) ++diff; // 本来是 0,现在要变正了
                ++cnt[out];
                if (cnt[out] == 0) --diff; // 恰好归零
            }

            if (right >= lp - 1 && diff == 0)
                ans.push_back(right - lp + 1);
        }
        return ans;
    }
};

// 本地测试:输入两个字符串 s 和 p;输出所有异位词的起始下标,空则输出 none
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, p;
    if (!(cin >> s >> p)) return 0;

    vector<int> ans = Solution().findAnagrams(s, p);
    if (ans.empty()) {
        cout << "none\n";
    } else {
        for (size_t i = 0; i < ans.size(); ++i)
            cout << ans[i] << (i + 1 == ans.size() ? '\n' : ' ');
    }
    return 0;
}