双指针专题(八)：步长跳跃的艺术——「串联所有单词的子串」-平芜编程栈

场景想象：

你有一串很长的珍珠项链（字符串 s），和一堆散落的、长度相同的宝石（单词数组 words）。

你需要从项链上截取一段，使得这段子串恰好由所有的宝石串联而成（顺序不限，但每个宝石都要用上，且不能多不能少）。

难点升级：

步长变化：以前left++和right++是挪动 1 个字符。现在，因为单词长度固定为k，我们每次必须挪动k个字符。
分组遍历：如果我们只从index=0开始每次跳k步，我们会漏掉从index=1开始的情况。所以我们需要错位触发。

力扣 30. 串联所有单词的子串

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

题目分析：

输入：字符串s，字符串数组words（words里所有单词长度相同，记为oneWordLen）。
目标：在s中找到所有起始索引，使得从该位置开始的子串恰好包含words中所有单词各一次。
输出：索引数组。

核心思维：多路滑动窗口 + HashMap 计数

这其实就是 LC 438 异位词的“巨人版”。

我们将 s 看作是一个由“单词”组成的数组。

假设单词长度 oneWordLen = 3。

我们需要分别从 0, 1, 2 这三个偏移量开始跑滑动窗口。

Offset 0: 检查s[0...2], s[3...5], s[6...8]...
Offset 1: 检查s[1...3], s[4...6], s[7...9]...
Offset 2: 检查s[2...4], s[5...7], s[8...10]...

这样就能覆盖所有可能的切分情况。

代码实现 (JavaScript)

JavaScript

/** * @param {string} s * @param {string[]} words * @return {number[]} */ var findSubstring = function(s, words) { if (!s || !words || words.length === 0) return []; const oneWordLen = words[0].length; const wordCount = words.length; // 总长度：所有单词拼起来有多长 const allWordsLen = oneWordLen * wordCount; const res = []; // 1. 统计 words 里的单词需求 const need = new Map(); for (const w of words) { need.set(w, (need.get(w) || 0) + 1); } // 2. 核心：外层循环控制“偏移量” (Offset) // 只要遍历 0 到 oneWordLen - 1 即可覆盖所有情况 // 比如单词长 3，我们只需要从 0, 1, 2 开始跑三次滑动窗口 for (let i = 0; i < oneWordLen; i++) { let left = i; let right = i; let count = 0; // 窗口内有效匹配的单词个数 const window = new Map(); // 当前窗口里的单词统计 // 内层循环：标准的滑动窗口，每次跳 oneWordLen 步 while (right + oneWordLen <= s.length) { // --- 进窗口 --- // 截取一个单词 const w = s.substring(right, right + oneWordLen); right += oneWordLen; // 指针大步跃进 // 如果这个单词不在需求列表里，说明这一段全废了 if (!need.has(w)) { // 直接清空窗口，从下一个位置重新开始 window.clear(); count = 0; left = right; } else { // 单词是有效的，加入窗口 window.set(w, (window.get(w) || 0) + 1); count++; // --- 出窗口 --- // 如果窗口里某个单词的数量超过了需求 // 比如 need={A:1}，window={A:2}，这时候必须缩左边，直到把多余的 A 吐出去 while (window.get(w) > need.get(w)) { const leftWord = s.substring(left, left + oneWordLen); window.set(leftWord, window.get(leftWord) - 1); count--; left += oneWordLen; // 左指针也大步跃进 } // --- 检查结果 --- // 如果单词数量够了，记录起始位置 if (count === wordCount) { res.push(left); } } } } return res; };

深度解析：为什么需要外层循环`i`？

这是这道题最难理解的点。

假设 s = "barfoothefoobarman", words = ["foo", "bar"] (长度3)。

如果不加外层循环，直接从 0 开始滑：
- 检查bar,foo,the... (索引 0, 3, 6...)
但是，如果答案是从索引 1 开始的呢？（虽然这题不是，但假设s = "afoo..."）
- 从 0 开始滑会读到afo,o...，完全错位。
所以，我们需要：
- i=0: 处理索引0, 3, 6, 9...的单词切分。
- i=1: 处理索引1, 4, 7, 10...的单词切分。
- i=2: 处理索引2, 5, 8, 11...的单词切分。
- i=3: 不需要了，因为它和i=0是重合的（只是少了一个单词）。