Day 15。
今天两道题分别是 Substring with Concatenation of All Words 和 Next Permutation。
一道是很典型的 字符串分组滑窗题，一道是经典的 排列构造题。

今天的关键词：分组滑窗、哈希计数、固定步长、字典序、逆序段、下一个排列。

🧠 LeetCode 30 – Substring with Concatenation of All Words

💡 思路总结

这题要求找到字符串 s 中所有起始位置，使得从该位置开始的子串，恰好由 words 中所有单词拼接而成，并且每个单词使用次数一致、顺序任意。

这题一眼看上去很乱，但关键在于：

每个单词长度相同

这意味着我们不是一个字符一个字符乱扫，而是可以：

  • 按单词长度分组
  • 每次移动一个单词长度
  • 用滑动窗口维护当前单词频次

你的思路非常好，核心就是：

按 0 ~ wordLen-1 的不同起点做分组滑窗

这题最难的地方，其实就是想到这个“分组”思路。

💻 代码实现

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

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if (s.empty() || words.empty()) return res;

        int wordLen = words[0].size();
        int wordCount = words.size();
        int totalLen = wordLen * wordCount;

        if (s.size() < totalLen) return res;

        unordered_map<string, int> need;
        for (auto &w : words) {
            need[w]++;
        }

        // 按照 0 ~ wordLen-1 的不同起点分组滑动
        for (int offset = 0; offset < wordLen; offset++) {
            unordered_map<string, int> window;
            int left = offset;
            int right = offset;
            int count = 0;  // 当前窗口内单词总数

            while (right + wordLen <= s.size()) {
                string word = s.substr(right, wordLen);
                right += wordLen;

                // 不是目标单词，窗口直接清空
                if (!need.count(word)) {
                    window.clear();
                    count = 0;
                    left = right;
                    continue;
                }

                // 加入窗口
                window[word]++;
                count++;

                // 如果某个单词超频了，就缩左边
                while (window[word] > need[word]) {
                    string leftWord = s.substr(left, wordLen);
                    window[leftWord]--;
                    left += wordLen;
                    count--;
                }

                // 如果窗口刚好包含全部单词
                if (count == wordCount) {
                    res.push_back(left);

                    // 继续滑动，移出左边第一个单词
                    string leftWord = s.substr(left, wordLen);
                    window[leftWord]--;
                    left += wordLen;
                    count--;
                }
            }
        }

        return res;
    }
};

📌 知识点总结

1️⃣ 这题不是普通滑窗，是“固定步长滑窗”

普通滑动窗口一般是：

  • right++
  • left++

但这题不一样，因为我们每次处理的是一个完整单词，所以窗口移动单位不是 1，而是：

wordLen

这就是这题很有辨识度的地方。

2️⃣ 为什么要分 offset

比如每个单词长度是 3，那可能的对齐方式只有三种：

  • 从下标 0 开始切
  • 从下标 1 开始切
  • 从下标 2 开始切

如果不按这三种方式分组，你的窗口就可能把单词切坏。

所以这里的：

for (int offset = 0; offset < wordLen; offset++)

是这题的灵魂之一。

3️⃣ need 和 window 是经典模板

你这里用了两个哈希表：

  • need：目标单词频次
  • window：当前窗口单词频次

这就是滑窗题非常常见的一套结构。

本质是在问：

当前窗口里的每种单词数量，是否和目标要求一致？

4️⃣ “超频”这个处理很关键

当某个单词加入后，出现：

window[word] > need[word]

就说明当前窗口里这个单词太多了。
这时候不能整窗推倒重来，而是应该：

  • 不断移动左边界
  • 直到这个单词频次恢复合法

这一段很能体现滑窗的味道。

5️⃣ 这题最难的是建模，不是代码量

你这题代码不算短，但真正难的不是写，而是想：

  • 能不能按单词长度切
  • 能不能按 offset 分组
  • 能不能把它转成滑窗统计问题

一旦建模对了，后面就顺了。

🔀 LeetCode 31 – Next Permutation

💡 思路总结

这题要求把当前排列变成“字典序下一个更大的排列”。
如果当前已经是最大的排列，就变成最小排列。

比如：

  • [1,2,3] -> [1,3,2]
  • [3,2,1] -> [1,2,3]
  • [1,1,5] -> [1,5,1]

这题看起来像规律题，实际上核心是：

尽可能小地变大

你的代码就是经典正解，分三步：

  1. 从右往左找第一个下降位置 i
  2. 从右往左找第一个比 nums[i] 大的数 j
  3. 交换后，把右边部分反转

💻 代码实现

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 2;

        // 1. 从右往左找第一个 nums[i] < nums[i+1]
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // 2. 如果找到了 pivot
        if (i >= 0) {
            int j = n - 1;

            // 从右往左找第一个比 nums[i] 大的数
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }

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

        // 3. 反转右边部分
        reverse(nums.begin() + i + 1, nums.end());
    }
};

📌 知识点总结

1️⃣ 为什么从右往左找

因为我们想得到的是：

刚刚好比当前排列大一点点

所以应该优先改动最右边那一段，这样整体变化最小。

从右往左找第一个满足：

nums[i] < nums[i+1]

的位置，就是在找“还能变大”的最靠右位置。

2️⃣ 右边为什么一定是降序

当你从右往左一直找到 i 的时候，说明 i 右边这一段已经是：

尽可能大的排列

也就是降序排列。

所以如果想要整体变大，只能先动 i 这个位置。

3️⃣ 为什么要找“刚好比它大”的数

找到 i 后，不能随便找个更大的数交换，而是要从右往左找第一个大于 nums[i] 的数。

因为右边本身是降序的，所以这个数就是：

右边所有比它大的数里，最小的那个

这样交换后，整体增长幅度最小，才符合“下一个排列”。

4️⃣ 为什么最后要反转右边部分

交换完之后，右边那一段仍然是降序的。
但我们想要的是：

在已经变大的前提下，让右边尽可能小

所以直接把右边反转成升序即可。

这一句：

reverse(nums.begin() + i + 1, nums.end());

就是这题的收尾精髓。

5️⃣ 这题是非常经典的“规律构造题”

它不是让你暴力枚举所有排列，而是让你直接利用字典序规律，原地得到下一个答案。

这种题的核心能力不是模拟，而是：

  • 观察结构
  • 找关键拐点
  • 最小化变动

🧩 今日总结

题目核心思想
LeetCode 30分组滑窗 + 哈希计数 + 固定步长匹配
LeetCode 31字典序规律 + 找拐点 + 交换 + 反转

今天两题都挺有代表性：

  • 30 是滑窗题里的进阶建模题
  • 31 是排列题里的经典规律题

🧠 今日收获

今天最值得记住的两个模型：

1. 固定长度切块类问题

如果题目里有这种特征：

  • 若干子串长度相同
  • 顺序处理块
  • 每次可以整块移动

那就要想到：

  • 按长度分组
  • 固定步长滑窗
  • 哈希表计数

2. “下一个 / 上一个” 构造类问题

看到这种题，可以优先想：

  • 哪一部分还能调整
  • 怎样调整才能变化最小
  • 剩余部分怎么恢复成最优结构

这题的核心就是：

尽量从右边动，尽量少变，变完后把后缀整理成最小。

💬 写给自己的话

Day 15 了。

十五天，说长不长，说短也不短。
但很明显，你已经在慢慢接触越来越“有套路感”的题了。

以前可能是看一题是一题，
现在会开始想：

  • 这是不是滑窗变形？
  • 这是不是某种字典序构造？
  • 这题核心是不是在找规律？

这就说明，你已经开始从“做题”走向“识别题型”了。

这一步特别重要。
因为真正会刷题的人，不是做过每一道题，
而是看到新题时，能迅速把它归到某一类里。

继续保持。
每天一点点，题感真的会越来越清晰。

阿玉，Day 15，继续冲。

—— 刷题第 15 天