子串
更新: 8/31/2025 字数: 0 字 时长: 0 分钟
和为 K 的子数组
java
/**
* <p>此方法使用暴力枚举所有可能的子数组，然后检查它们的和是否等于 {@code k}。</p>
* <p>一个子数组由其起始索引和结束索引唯一确定。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>初始化计数器 {@code count = 0}，用于记录和为 {@code k} 的子数组个数。</li>
* <li>使用外层循环 {@code i} 从 {@code 0} 遍历到 {@code n-1}，表示子数组的起始索引。</li>
* <li>使用内层循环 {@code j} 从 {@code i} 遍历到 {@code n-1}，表示子数组的结束索引。
* <ul>
* <li>在内层循环中，维护一个变量 {@code currentSum}，它表示从 {@code nums[i]} 到 {@code nums[j]} 的子数组的和。</li>
* <li>每次 {@code j} 递增时，将 {@code nums[j]} 添加到 {@code currentSum} 中。</li>
* <li>如果 {@code currentSum == k}，则说明找到了一个符合条件的子数组，将 {@code count} 递增 1。</li>
* </ul>
* </li>
* <li>循环结束后，返回 {@code count}。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n^2)}。
* <ul>
* <li>外层循环执行 {@code n} 次。</li>
* <li>内层循环在最坏情况下也执行 {@code n} 次。</li>
* <li>每次内层循环中的操作（加法和比较）都是 {@code O(1)}。</li>
* <li>因此，总时间复杂度为 {@code O(n * n) = O(n^2)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>除了存储输入数组和返回结果所需的空间外，只使用了常数个额外变量。</li>
* </ul>
* </li>
* </ul>
*
* @param nums 输入的整数数组。
* @param k 目标和。
* @return 数组中和为 {@code k} 的子数组的个数。
*/
public int subarraySum(int[] nums, int k) {
int n = nums.length;
int count = 0; // 记录和为 k 的子数组个数
// i 作为子数组的起始索引
for (int i = 0; i < n; i++) {
int currentSum = 0; // 当前子数组的和
// j 作为子数组的结束索引
// 子数组为 nums[i...j]
for (int j = i; j < n; j++) {
currentSum += nums[j]; // 累加当前元素到子数组的和中
// 如果当前子数组的和等于 k，则找到一个符合条件的子数组
if (currentSum == k) {
count++;
}
}
}
return count;
}java
/**
* <p>此方法利用前缀和和哈希表来高效地解决和为 {@code k} 的子数组问题。</p>
* <p>核心思想：如果一个子数组 {@code nums[i...j]} 的和为 {@code k}，那么其前缀和 {@code sum[j]} 减去前缀和 {@code sum[i-1]} 应该等于 {@code k}。
* 即 {@code sum[j] - sum[i-1] = k}，这等价于 {@code sum[i-1] = sum[j] - k}。</p>
* <p>我们遍历数组，计算每个位置的前缀和，并使用哈希表存储每个前缀和出现的次数。
* 当计算到当前前缀和 {@code currentSum} 时，我们查询哈希表中是否存在 {@code (currentSum - k)} 这个前缀和。
* 如果存在，那么所有以 {@code currentSum - k} 结尾的前缀和，它们之后到当前位置 {@code currentSum} 之间形成的子数组的和都为 {@code k}。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>初始化计数器 {@code count = 0}，用于记录和为 {@code k} 的子数组个数。</li>
* <li>初始化当前前缀和 {@code currentSum = 0}。</li>
* <li>创建一个哈希表 {@code prefixSumCount = new HashMap<Integer, Integer>()}，用于存储：
* <ul>
* <li>键：前缀和的值。</li>
* <li>值：该前缀和出现的次数。</li>
* </ul>
* </li>
* <li><strong>初始化哈希表：</strong> 将 {@code (0, 1)} 存入 {@code prefixSumCount}。
* <ul>
* <li>这表示在数组开始之前（索引 -1），前缀和为 0 的情况出现了一次。这对于处理从数组第一个元素开始的子数组 (即 {@code sum[j] - sum[-1] = k} 变成 {@code sum[j] - 0 = k}) 至关重要。</li>
* </ul>
* </li>
* <li>遍历数组 {@code nums} 的每个元素 {@code num} (或通过索引 {@code i})：
* <ul>
* <li>将 {@code num} 加到 {@code currentSum} 中，更新当前前缀和。</li>
* <li>在哈希表中查找是否存在键为 {@code (currentSum - k)} 的项。
* <ul>
* <li>如果存在，说明之前存在一个前缀和为 {@code (currentSum - k)} 的位置。那么从该位置的下一个元素到当前元素所形成的子数组的和就是 {@code k}。</li>
* <li>将 {@code count} 加上 {@code prefixSumCount.get(currentSum - k)} (即符合条件的子数组个数)。</li>
* </ul>
* </li>
* <li>将当前的 {@code currentSum} 及其出现次数存入或更新到 {@code prefixSumCount} 中。
* <ul>
* <li>{@code prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1)}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li>循环结束后，返回 {@code count}。</li>
* </ol>
*
* <h3>核心思想：</h3>
* <p>如果 {@code sum[j]} 是从 {@code nums[0]} 到 {@code nums[j]} 的和，{@code sum[i-1]} 是从 {@code nums[0]} 到 {@code nums[i-1]} 的和。</p>
* <p>那么子数组 {@code nums[i...j]} 的和就是 {@code sum[j] - sum[i-1]}。</p>
* <p>我们想找到 {@code sum[j] - sum[i-1] = k} 的情况。这等价于 {@code sum[i-1] = sum[j] - k}。</p>
* <p>因此，当我们遍历到 {@code j} 计算出 {@code currentSum = sum[j]} 时，我们只需要检查之前是否有 {@code sum[i-1] = currentSum - k} 出现过，以及出现过多少次。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>我们只遍历数组一次。</li>
* <li>在每次迭代中，哈希表的 {@code put}、{@code get} 和 {@code containsKey} 操作的平均时间复杂度为 {@code O(1)}。</li>
* <li>因此，总时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>在最坏情况下（例如，所有前缀和都不同），哈希表中会存储 {@code n} 个不同的前缀和。</li>
* <li>因此，空间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* </ul>
*
* @param nums 输入的整数数组。
* @param k 目标和。
* @return 数组中和为 {@code k} 的子数组的个数。
*/
public int subarraySum(int[] nums, int k) {
int count = 0; // 记录和为 k 的子数组个数
int currentSum = 0; // 记录当前的前缀和
// 使用哈希表存储前缀和及其出现的次数
// key: 前缀和的值
// value: 该前缀和出现的次数
Map<Integer, Integer> prefixSumCount = new HashMap<>();
// 初始化：前缀和为 0 的情况出现一次 (对应空前缀，即在数组开始前)
// 这一步非常关键，因为它允许我们处理从数组第一个元素开始的子数组
// 例如，如果 nums = [k], k = k，那么 currentSum 第一次就等于 k。
// 此时我们要找 currentSum - k = 0 的前缀和，如果 0 出现了 1 次，count 就会加 1。
prefixSumCount.put(0, 1);
for (int num : nums) {
currentSum += num; // 更新当前前缀和
// 如果哈希表中存在 (currentSum - k) 这个前缀和
// 那么从 (currentSum - k) 对应的位置到当前位置 num 之间形成的子数组的和就是 k
if (prefixSumCount.containsKey(currentSum - k)) {
// 将符合条件的子数组的个数累加到 count 中
count += prefixSumCount.get(currentSum - k);
}
// 将当前的 currentSum 及其出现次数存入或更新到哈希表中
prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
}
return count;
}滑动窗口最大值
java
/**
* <p>此方法使用双端队列（{@link java.util.ArrayDeque}）来高效地找到滑动窗口中的最大值。</p>
* <p>双端队列中存储的是元素的索引，并且这些索引对应的元素值是单调递减的。</p>
* <p>通过维护一个这样的单调递减队列，我们可以确保队列的头部始终是当前窗口中的最大值的索引。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li><strong>预处理与边界检查：</strong>
* <ul>
* <li>获取数组 {@code nums} 的长度 {@code n}。</li>
* <li>如果 {@code nums} 为空或者 {@code k} 为 {@code 0}，则直接返回空数组（或抛出异常，取决于具体要求）。</li>
* <li>初始化一个结果数组 {@code result}，其大小为 {@code (n - k + 1)}，用于存储每个滑动窗口的最大值。</li>
* <li>创建一个双端队列 {@code deque = new ArrayDeque<Integer>()}，用于存储窗口内元素的索引。</li>
* </ul>
* </li>
* <li><strong>初始化第一个滑动窗口（前 {@code k} 个元素）：</strong>
* <ul>
* <li>遍历 {@code nums} 的前 {@code k} 个元素（索引从 {@code 0} 到 {@code k-1}）：
* <ul>
* <li><strong>移除队列尾部小于当前元素的元素：</strong> 当双端队列不为空且当前元素 {@code nums[i]} 大于等于队列尾部索引对应的元素 {@code nums[deque.peekLast()]} 时，将队列尾部元素弹出。这是为了维护队列的单调递减特性，确保队列中只保留可能成为最大值的元素。</li>
* <li><strong>将当前元素索引入队：</strong> 将当前元素的索引 {@code i} 添加到双端队列的尾部。</li>
* </ul>
* </li>
* <li>将第一个窗口的最大值（即队列头部索引对应的元素）存储到 {@code result[0]} 中。</li>
* </ul>
* </li>
* <li><strong>滑动窗口并更新最大值（从第 {@code k} 个元素开始）：</strong>
* <ul>
* <li>使用一个循环，变量 {@code i} 从 {@code k} 开始遍历到 {@code n-1}。{@code i} 代表滑动窗口的右边界（即新进入窗口的元素的索引）。</li>
* <li>在每次循环中：
* <ul>
* <li><strong>移除过期元素：</strong> 如果队列头部索引 {@code deque.peekFirst()} 已经超出了当前滑动窗口的左边界（即 {@code deque.peekFirst() <= i - k}），则将队列头部元素弹出。</li>
* <li><strong>维护单调递减队列：</strong> 当双端队列不为空且当前元素 {@code nums[i]} 大于等于队列尾部索引对应的元素 {@code nums[deque.peekLast()]} 时，将队列尾部元素弹出。</li>
* <li><strong>将当前元素索引入队：</strong> 将当前元素的索引 {@code i} 添加到双端队列的尾部。</li>
* <li><strong>记录当前窗口最大值：</strong> 当前窗口的最大值就是队列头部索引对应的元素 {@code nums[deque.peekFirst()]}。将其存储到 {@code result[i - k + 1]} 中。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li>循环结束后，返回 {@code result} 数组。</li>
* </ol>
*
* <h3>双端队列的特性：</h3>
* <ul>
* <li>队列中存储的是窗口内元素的<strong>索引</strong>。</li>
* <li>队列中的元素<strong>从头到尾对应的数值是单调递减的</strong>。</li>
* <li><strong>队列头部：</strong> 始终是当前窗口中最大值的索引。</li>
* <li><strong>队列尾部：</strong> 负责接收新元素，并维护单调性。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>每个元素 {@code nums[i]} 最多被添加到双端队列一次，也最多被从双端队列中移除一次（从头部或尾部）。</li>
* <li>双端队列的添加、移除和获取头部/尾部元素的操作都是 {@code O(1)}。</li>
* <li>因此，总时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(k)}。
* <ul>
* <li>双端队列在最坏情况下（例如，窗口内的元素单调递增）会存储 {@code k} 个元素的索引。</li>
* <li>因此，空间复杂度为 {@code O(k)}。</li>
* </ul>
* </li>
* </ul>
*
* @param nums 输入的整数数组。
* @param k 滑动窗口的大小。
* @return 一个整数数组，包含每个滑动窗口中的最大值。
*/
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) {
return new int[0];
}
// 结果数组，大小为 n - k + 1
int[] result = new int[n - k + 1];
// 双端队列，存储元素在 nums 中的索引，保证队列中的索引对应的元素值单调递减
Deque<Integer> deque = new ArrayDeque<>();
// 1. 初始化第一个滑动窗口 (前 k 个元素)
for (int i = 0; i < k; i++) {
// 移除所有小于等于当前元素的队尾元素，确保队首是最大值且队列单调递减
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.removeLast();
}
// 将当前元素的索引加入队尾
deque.addLast(i);
}
// 记录第一个窗口的最大值 (队列头部就是当前窗口最大值的索引)
result[0] = nums[deque.peekFirst()];
// 2. 滑动窗口，从第 k 个元素开始遍历到数组末尾
// i 是当前窗口的右边界
for (int i = k; i < n; i++) {
// 移除队头已不在当前窗口范围内的元素
// 如果队头索引 <= i - k，说明队头元素已过期
if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.removeFirst();
}
// 移除所有小于等于当前元素的队尾元素，维护队列的单调递减性
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.removeLast();
}
// 将当前元素的索引加入队尾
deque.addLast(i);
// 记录当前窗口的最大值 (队列头部是当前窗口最大值的索引)
// result 的索引是 (i - k + 1)，表示当前窗口的起始索引
result[i - k + 1] = nums[deque.peekFirst()];
}
return result;
}最小覆盖子串
java
/**
* <p>此方法使用滑动窗口和哈希表（{@link HashMap}）来找到字符串 {@code s} 中涵盖 {@code t} 所有字符的最小子串。</p>
* <p>核心思想是维护一个滑动窗口，记录窗口内字符的频率，并与 {@code t} 中字符的所需频率进行比较。</p>
* <p>当窗口内字符满足 {@code t} 的所有要求时，尝试收缩左边界以寻找最小子串。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li><strong>预处理：</strong>
* <ul>
* <li>如果 {@code t} 为空，直接返回空字符串。</li>
* <li>初始化一个哈希表 {@code tMap}，用于存储字符串 {@code t} 中每个字符及其所需频率。</li>
* <li>遍历 {@code t}，填充 {@code tMap}。</li>
* </ul>
* </li>
* <li><strong>初始化变量：</strong>
* <ul>
* <li>{@code left = 0}：滑动窗口的左边界。</li>
* <li>{@code minLen = Integer.MAX_VALUE}：记录找到的最小覆盖子串的长度，初始化为最大值。</li>
* <li>{@code minStart = 0}：记录最小覆盖子串的起始索引。</li>
* <li>{@code windowMap = new HashMap<Character, Integer>()}：一个哈希表，用于存储当前滑动窗口中每个字符的频率。</li>
* <li>{@code matchCount = 0}：一个计数器，表示当前窗口中有多少个字符（及其频率）满足了 {@code tMap} 中的要求。当 {@code matchCount == tMap.size()} 时，表示窗口包含了 {@code t} 的所有字符。</li>
* </ul>
* </li>
* <li><strong>滑动窗口：</strong>
* <ul>
* <li>使用 {@code right} 指针从 {@code 0} 遍历到 {@code s.length() - 1}，作为滑动窗口的右边界。</li>
* <li>在每次 {@code right} 移动时，执行以下操作：
* <ul>
* <li><strong>扩展窗口：</strong>
* <ul>
* <li>获取当前字符 {@code charRight = s.charAt(right)}。</li>
* <li>更新 {@code windowMap} 中 {@code charRight} 的频率。</li>
* <li>如果 {@code tMap} 中包含 {@code charRight}，并且 {@code windowMap.get(charRight)} 等于 {@code tMap.get(charRight)}（这意味着 {@code charRight} 的频率在窗口中已达到 {@code t} 的要求），则将 {@code matchCount} 递增 1。</li>
* </ul>
* </li>
* <li><strong>收缩窗口（当满足条件时）：</strong>
* <ul>
* <li>当 {@code matchCount == tMap.size()} 时，表示当前窗口已经覆盖了 {@code t} 的所有字符。此时，尝试收缩左边界 {@code left} 以寻找更小的子串：
* <ul>
* <li>计算当前窗口的长度 {@code currentLen = right - left + 1}。</li>
* <li>如果 {@code currentLen < minLen}，则更新 {@code minLen = currentLen} 和 {@code minStart = left}。</li>
* <li>获取左边界字符 {@code charLeft = s.charAt(left)}。</li>
* <li>从 {@code windowMap} 中移除 {@code charLeft}（更新其频率）。</li>
* <li>如果 {@code tMap} 中包含 {@code charLeft}，并且 {@code windowMap.get(charLeft)} 小于 {@code tMap.get(charLeft)}（这意味着移除该字符后，窗口不再满足 {@code charLeft} 的频率要求），则将 {@code matchCount} 递减 1。</li>
* <li>将 {@code left} 指针右移一位。</li>
* </ul>
* </li>
* <li>继续收缩，直到 {@code matchCount} 不再等于 {@code tMap.size()}。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>如果 {@code minLen} 仍然是 {@code Integer.MAX_VALUE}，说明没有找到符合条件的子串，返回空字符串 {@code "" }。</li>
* <li>否则，返回 {@code s.substring(minStart, minStart + minLen)}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>优化点：</h3>
* <ul>
* <li>使用两个哈希表（或数组）分别存储 {@code t} 的字符频率和滑动窗口的字符频率。</li>
* <li>使用一个 {@code matchCount} 变量来快速判断当前窗口是否已经覆盖了 {@code t} 的所有字符，避免每次都遍历哈希表进行比较。</li>
* <li>先扩展窗口，直到满足条件，然后收缩窗口，直到不满足条件，从而有效地寻找最小子串。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(s.length() + t.length())}。
* <ul>
* <li>遍历 {@code t} 构建 {@code tMap} 需要 {@code O(t.length())}。</li>
* <li>滑动窗口的 {@code right} 指针遍历 {@code s} 一次，{@code left} 指针最多遍历 {@code s} 一次。</li>
* <li>哈希表的 {@code put}、{@code get}、{@code containsKey} 操作平均时间复杂度为 {@code O(1)}。</li>
* <li>因此，总时间复杂度为 {@code O(s.length() + t.length())}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(k)}，其中 {@code k} 是字符集的大小（例如，对于 ASCII 字符集，{@code k = 128}）。
* <ul>
* <li>{@code tMap} 和 {@code windowMap} 在最坏情况下会存储不同字符集中的所有字符。</li>
* <li>如果字符集是英文字母，则可以使用大小为 52 (大小写) 或 128/256 的数组替代 {@link HashMap}，将空间复杂度优化为 {@code O(1)}。</li>
* </ul>
* </li>
* </ul>
*
* @param s 源字符串。
* @param t 目标字符串，包含需要被覆盖的字符。
* @return {@code s} 中涵盖 {@code t} 所有字符的最小子串，如果不存在则返回空字符串。
*/
public String minWindow(String s, String t) {
if (t.isEmpty()) {
return "";
}
// 存储 t 中每个字符及其所需频率
Map<Character, Integer> tMap = new HashMap<>();
for (char c : t.toCharArray()) {
tMap.put(c, tMap.getOrDefault(c, 0) + 1);
}
int left = 0; // 滑动窗口左边界
int minLen = Integer.MAX_VALUE; // 记录最小覆盖子串的长度
int minStart = 0; // 记录最小覆盖子串的起始索引
// 存储当前滑动窗口中每个字符的频率
Map<Character, Integer> windowMap = new HashMap<>();
// 记录当前窗口中有多少个字符（及其频率）满足了 tMap 中的要求
int matchCount = 0; // 当 matchCount == tMap.size() 时，表示窗口已覆盖 t 的所有字符
// right 指针遍历 s，扩展滑动窗口
for (int right = 0; right < s.length(); right++) {
char charRight = s.charAt(right);
// 1. 扩展窗口：将 charRight 加入窗口
windowMap.put(charRight, windowMap.getOrDefault(charRight, 0) + 1);
// 如果 charRight 是 t 中需要的字符，且其在窗口中的频率达到了 t 的要求
if (tMap.containsKey(charRight) && windowMap.get(charRight).equals(tMap.get(charRight))) {
matchCount++;
}
// 2. 尝试收缩窗口：当窗口已经覆盖了 t 的所有字符时
while (matchCount == tMap.size()) {
// 更新最小子串信息
int currentLen = right - left + 1;
if (currentLen < minLen) {
minLen = currentLen;
minStart = left;
}
// 准备收缩左边界
char charLeft = s.charAt(left);
windowMap.put(charLeft, windowMap.get(charLeft) - 1); // 从窗口中移除 charLeft
// 如果 charLeft 是 t 中需要的字符，且移除后其在窗口中的频率不再满足 t 的要求
if (tMap.containsKey(charLeft) && windowMap.get(charLeft) < tMap.get(charLeft)) {
matchCount--; // 匹配数减 1
}
left++; // 左边界右移
}
}
// 根据 minLen 判断是否找到子串并返回
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}贡献者
LI SIR