企业官网建设流程全解析

目录

1. 题目解析

2. 讲解算法原理

3. 代码实现（完整保留）

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

1. 题目解析

题目：串联所有单词的子串

给定一个字符串s和一个单词数组words，words中所有单词长度相同。要求找出s中串联子串的起始位置——即包含words中所有单词（顺序不限）连续拼接而成的子串。

• 示例1：

  输入：s = "barfoothefoobarman",words = ["foo","bar"]

  输出：[0,9]

  解释：words长度为2，words[0]长度为3，故子串长度需为2×3=6。

  • 子串"barfoo"从位置0开始，是["bar","foo"]的排列；

  • 子串"foobar"从位置9开始，是["foo","bar"]的排列。

    返回顺序无关，如[9,0]也可。

2. 讲解算法原理

解法：滑动窗口 + 哈希表

参考类似题目（如438. 找出所有的字母异位词），本题核心是用滑动窗口覆盖所有单词的拼接，并通过哈希表统计单词频次。

• 关键思路：

  1. 哈希表：用hash1存words中每个单词的出现次数；用hash2存滑动窗口内单词的出现次数。

  2. 指针移动：左指针left、右指针right按单词长度（len）移动（因为单词长度固定）。

  3. 滑动窗口执行次数：外层循环次数为len（因为单词长度可能为1~len，需覆盖所有可能的起始偏移）。

示意图理解：

• 示例：s = "barfoothefoobarman",words = ["foo","bar"]

• 滑动窗口的移动，以及hash1（words频次）、hash2（窗口内频次）的对比。

3. 代码实现（完整保留）

class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> ret = new ArrayList<Integer>(); Map<String, Integer> hash1 = new HashMap<String, Integer>(); // 保存字典中所有单词的频次 for (String str : words) hash1.put(str, hash1.getOrDefault(str, 0) + 1); int len = words[0].length(), m = words.length; for (int i = 0; i < len; i++) { // 执行次数：单词长度的循环 Map<String, Integer> hash2 = new HashMap<String, Integer>(); // 保存窗口内所有单词的频次 for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) { // 进窗口 + 维护 count String in = s.substring(right, right + len); hash2.put(in, hash2.getOrDefault(in, 0) + 1); if (hash2.get(in) <= hash1.getOrDefault(in, 0)) count++; // 出窗口条件：窗口长度超过 单词总长度（len*m） if (right - left + 1 > len * m) { String out = s.substring(left, left + len); if (hash2.get(out) <= hash1.getOrDefault(out, 0)) count--; hash2.put(out, hash2.get(out) - 1); left += len; } // 更新结果：count等于单词总数m时，记录left if (count == m) ret.add(left); } } return ret; } }