你好我是fengxin_rou这是我的个人主页fengxin_rou的主页❄️欢迎查看我的专栏我的专栏《Java后端学习》、《JAVASE基础》、《JUC并发》、《redis》、《JVM虚拟机》、《MYSQL》、《黑马点评》、《rabbitmq》、《JavaWebAI的talis学习系统》、《苍穹外卖》目录前言一、滑动窗口算法找到字符串中所有字母异位词1.1 问题背景与核心痛点1.2 算法原理字符计数 窗口滑动1.3 完整 Java 代码实现编辑1.4 关键细节与避坑指南二、前缀和算法统计和为 K 的子数组2.1 问题背景与核心痛点2.2 算法原理前缀和定义 哈希表计数2.3 完整 Java 代码实现编辑2.4 关键细节与避坑指南三、两大算法对比与应用场景分析3.1 核心特性对比3.2 实际应用场景四、性能优化与扩展思考4.1 滑动窗口优化4.2 前缀和优化结语前言在算法面试与刷题中字符串匹配与子数组求和是高频考点。本文将详解两道典型题字母异位词匹配与子数组和统计带你掌握滑动窗口与前缀和两大核心算法高效解决这类问题。一、滑动窗口算法找到字符串中所有字母异位词1.1 问题背景与核心痛点LeetCode 438 题要求在字符串s中找到所有与字符串p的异位词匹配的子串起始索引。 异位词指由相同字母以不同顺序排列组成的字符串传统暴力匹配会因重复统计字符而效率低下滑动窗口是最优解。1.2 算法原理字符计数 窗口滑动滑动窗口的核心思想是维护一个与p长度相同的窗口通过字符计数数组统计窗口内字母出现次数再与p的计数对比实现 O (n) 时间复杂度匹配。边界判断若s长度小于p直接返回空列表避免无效计算。初始化计数用两个长度为 26 的数组分别统计p和s中首个窗口的字母出现次数。初始窗口校验对比两个计数数组若相同则将索引 0 加入结果。窗口滑动每次移动窗口减去移出字符的计数增加移入字符的计数再校验数组是否匹配。1.3 完整 Java 代码实现import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public ListInteger findAnagrams(String s, String p) { int sLen s.length(), pLen p.length(); // 边界条件s长度小于p不可能存在异位词 if (sLen pLen) { return new ArrayList(); } ListInteger ans new ArrayList(); // 统计s和p中字母出现次数仅小写字母 int[] sCount new int[26]; int[] pCount new int[26]; // 初始化第一个窗口的计数 for (int i 0; i pLen; i) { sCount[s.charAt(i) - a]; pCount[p.charAt(i) - a]; } // 检查初始窗口是否匹配 if (Arrays.equals(sCount, pCount)) { ans.add(0); } // 滑动窗口每次移动一位更新计数并校验 for (int i 0; i sLen - pLen; i) { // 移出窗口左侧字符 --sCount[s.charAt(i) - a]; // 移入窗口右侧新字符 sCount[s.charAt(i pLen) - a]; // 校验当前窗口是否匹配异位词 if (Arrays.equals(sCount, pCount)) { ans.add(i 1); } } return ans; } }1.4 关键细节与避坑指南字符计数优化使用长度为 26 的数组代替哈希表利用字母与a的偏移直接索引效率更高。数组对比效率Arrays.equals直接对比两个计数数组避免手动遍历代码更简洁。窗口移动边界循环终止条件为sLen - pLen确保窗口不会超出字符串s的范围。二、前缀和算法统计和为 K 的子数组2.1 问题背景与核心痛点LeetCode 560 题要求统计数组中连续子数组和等于k的个数。 数组中存在负数时滑动窗口的单调性失效无法直接使用暴力枚举子数组则时间复杂度为 O (n²)效率低下前缀和 哈希表是最优解。2.2 算法原理前缀和定义 哈希表计数前缀和指数组前i个元素的和定义preSum[i]为前i个元素的和子数组[j, i]的和可表示为preSum[i1] - preSum[j]。 要使子数组和为k即preSum[i1] - preSum[j] k等价于preSum[j] preSum[i1] - k。 用哈希表记录每个前缀和出现的次数遍历前缀和时统计满足条件的preSum[j]数量即可。2.3 完整 Java 代码实现import java.util.HashMap; class Solution { public int subarraySum(int[] nums, int k) { // 前缀和数组preSum[0] 0preSum[i]为前i个元素的和 int[] preSum new int[nums.length 1]; preSum[0] 0; for (int i 0; i nums.length; i) { preSum[i 1] preSum[i] nums[i]; } int ans 0; // 哈希表key为前缀和value为该前缀和出现的次数 HashMapInteger, Integer preSumCount new HashMap(); for (int sj : preSum) { // 寻找满足 si sj - k 的前缀和次数 int si sj - k; if (preSumCount.containsKey(si)) { ans preSumCount.get(si); } // 将当前前缀和加入哈希表更新计数 preSumCount.put(sj, preSumCount.getOrDefault(sj, 0) 1); } return ans; } }2.4 关键细节与避坑指南前缀和初始化preSum[0] 0是关键处理从数组开头到当前位置的子数组和为k的情况。哈希表更新顺序先查询si sj - k的次数再将当前前缀和sj加入哈希表避免重复统计。处理负数与 0前缀和 哈希表天然支持数组中存在负数、0 的场景无需额外处理。三、两大算法对比与应用场景分析3.1 核心特性对比表格算法时间复杂度空间复杂度适用场景滑动窗口O(n)O (1)固定长度窗口字符串匹配、定长子数组问题元素为正数或有固定窗口长度前缀和 哈希表O(n)O(n)不定长子数组和问题含负数、0 的数组无法用滑动窗口的场景3.2 实际应用场景滑动窗口可扩展到最长无重复子串、最小覆盖子串等字符串问题也可用于定长滑动窗口的统计类问题。前缀和广泛应用于数组区间和查询、子数组统计问题结合哈希表可高效解决带条件的子数组计数。四、性能优化与扩展思考4.1 滑动窗口优化在字母异位词问题中可进一步优化用一个变量记录窗口内与p字符计数不同的字母数量避免每次对比数组将常数时间进一步降低。当s中出现非小写字母时可扩展计数数组大小或用哈希表兼容所有字符。4.2 前缀和优化在子数组和问题中可直接在遍历数组时计算前缀和并更新哈希表无需额外创建前缀和数组节省空间public int subarraySum(int[] nums, int k) { HashMapInteger, Integer map new HashMap(); map.put(0, 1); int preSum 0, ans 0; for (int num : nums) { preSum num; ans map.getOrDefault(preSum - k, 0); map.put(preSum, map.getOrDefault(preSum, 0) 1); } return ans; }结语滑动窗口与前缀和是解决字符串匹配与子数组问题的核心算法。滑动窗口通过维护固定窗口实现高效字符统计适用于定长匹配场景前缀和 哈希表则解决了含负数的子数组和问题是不定长区间问题的通用方案。掌握这两种算法的核心原理与实现细节能大幅提升刷题效率与面试竞争力。后续可进一步学习滑动窗口的可变长度实现、二维前缀和等扩展应用深入理解算法思想的本质。
【滑动窗口与前缀和算法实战】：LeetCode560.438 高频题深度解析
你好我是fengxin_rou这是我的个人主页fengxin_rou的主页❄️欢迎查看我的专栏我的专栏《Java后端学习》、《JAVASE基础》、《JUC并发》、《redis》、《JVM虚拟机》、《MYSQL》、《黑马点评》、《rabbitmq》、《JavaWebAI的talis学习系统》、《苍穹外卖》目录前言一、滑动窗口算法找到字符串中所有字母异位词1.1 问题背景与核心痛点1.2 算法原理字符计数 窗口滑动1.3 完整 Java 代码实现编辑1.4 关键细节与避坑指南二、前缀和算法统计和为 K 的子数组2.1 问题背景与核心痛点2.2 算法原理前缀和定义 哈希表计数2.3 完整 Java 代码实现编辑2.4 关键细节与避坑指南三、两大算法对比与应用场景分析3.1 核心特性对比3.2 实际应用场景四、性能优化与扩展思考4.1 滑动窗口优化4.2 前缀和优化结语前言在算法面试与刷题中字符串匹配与子数组求和是高频考点。本文将详解两道典型题字母异位词匹配与子数组和统计带你掌握滑动窗口与前缀和两大核心算法高效解决这类问题。一、滑动窗口算法找到字符串中所有字母异位词1.1 问题背景与核心痛点LeetCode 438 题要求在字符串s中找到所有与字符串p的异位词匹配的子串起始索引。 异位词指由相同字母以不同顺序排列组成的字符串传统暴力匹配会因重复统计字符而效率低下滑动窗口是最优解。1.2 算法原理字符计数 窗口滑动滑动窗口的核心思想是维护一个与p长度相同的窗口通过字符计数数组统计窗口内字母出现次数再与p的计数对比实现 O (n) 时间复杂度匹配。边界判断若s长度小于p直接返回空列表避免无效计算。初始化计数用两个长度为 26 的数组分别统计p和s中首个窗口的字母出现次数。初始窗口校验对比两个计数数组若相同则将索引 0 加入结果。窗口滑动每次移动窗口减去移出字符的计数增加移入字符的计数再校验数组是否匹配。1.3 完整 Java 代码实现import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public ListInteger findAnagrams(String s, String p) { int sLen s.length(), pLen p.length(); // 边界条件s长度小于p不可能存在异位词 if (sLen pLen) { return new ArrayList(); } ListInteger ans new ArrayList(); // 统计s和p中字母出现次数仅小写字母 int[] sCount new int[26]; int[] pCount new int[26]; // 初始化第一个窗口的计数 for (int i 0; i pLen; i) { sCount[s.charAt(i) - a]; pCount[p.charAt(i) - a]; } // 检查初始窗口是否匹配 if (Arrays.equals(sCount, pCount)) { ans.add(0); } // 滑动窗口每次移动一位更新计数并校验 for (int i 0; i sLen - pLen; i) { // 移出窗口左侧字符 --sCount[s.charAt(i) - a]; // 移入窗口右侧新字符 sCount[s.charAt(i pLen) - a]; // 校验当前窗口是否匹配异位词 if (Arrays.equals(sCount, pCount)) { ans.add(i 1); } } return ans; } }1.4 关键细节与避坑指南字符计数优化使用长度为 26 的数组代替哈希表利用字母与a的偏移直接索引效率更高。数组对比效率Arrays.equals直接对比两个计数数组避免手动遍历代码更简洁。窗口移动边界循环终止条件为sLen - pLen确保窗口不会超出字符串s的范围。二、前缀和算法统计和为 K 的子数组2.1 问题背景与核心痛点LeetCode 560 题要求统计数组中连续子数组和等于k的个数。 数组中存在负数时滑动窗口的单调性失效无法直接使用暴力枚举子数组则时间复杂度为 O (n²)效率低下前缀和 哈希表是最优解。2.2 算法原理前缀和定义 哈希表计数前缀和指数组前i个元素的和定义preSum[i]为前i个元素的和子数组[j, i]的和可表示为preSum[i1] - preSum[j]。 要使子数组和为k即preSum[i1] - preSum[j] k等价于preSum[j] preSum[i1] - k。 用哈希表记录每个前缀和出现的次数遍历前缀和时统计满足条件的preSum[j]数量即可。2.3 完整 Java 代码实现import java.util.HashMap; class Solution { public int subarraySum(int[] nums, int k) { // 前缀和数组preSum[0] 0preSum[i]为前i个元素的和 int[] preSum new int[nums.length 1]; preSum[0] 0; for (int i 0; i nums.length; i) { preSum[i 1] preSum[i] nums[i]; } int ans 0; // 哈希表key为前缀和value为该前缀和出现的次数 HashMapInteger, Integer preSumCount new HashMap(); for (int sj : preSum) { // 寻找满足 si sj - k 的前缀和次数 int si sj - k; if (preSumCount.containsKey(si)) { ans preSumCount.get(si); } // 将当前前缀和加入哈希表更新计数 preSumCount.put(sj, preSumCount.getOrDefault(sj, 0) 1); } return ans; } }2.4 关键细节与避坑指南前缀和初始化preSum[0] 0是关键处理从数组开头到当前位置的子数组和为k的情况。哈希表更新顺序先查询si sj - k的次数再将当前前缀和sj加入哈希表避免重复统计。处理负数与 0前缀和 哈希表天然支持数组中存在负数、0 的场景无需额外处理。三、两大算法对比与应用场景分析3.1 核心特性对比表格算法时间复杂度空间复杂度适用场景滑动窗口O(n)O (1)固定长度窗口字符串匹配、定长子数组问题元素为正数或有固定窗口长度前缀和 哈希表O(n)O(n)不定长子数组和问题含负数、0 的数组无法用滑动窗口的场景3.2 实际应用场景滑动窗口可扩展到最长无重复子串、最小覆盖子串等字符串问题也可用于定长滑动窗口的统计类问题。前缀和广泛应用于数组区间和查询、子数组统计问题结合哈希表可高效解决带条件的子数组计数。四、性能优化与扩展思考4.1 滑动窗口优化在字母异位词问题中可进一步优化用一个变量记录窗口内与p字符计数不同的字母数量避免每次对比数组将常数时间进一步降低。当s中出现非小写字母时可扩展计数数组大小或用哈希表兼容所有字符。4.2 前缀和优化在子数组和问题中可直接在遍历数组时计算前缀和并更新哈希表无需额外创建前缀和数组节省空间public int subarraySum(int[] nums, int k) { HashMapInteger, Integer map new HashMap(); map.put(0, 1); int preSum 0, ans 0; for (int num : nums) { preSum num; ans map.getOrDefault(preSum - k, 0); map.put(preSum, map.getOrDefault(preSum, 0) 1); } return ans; }结语滑动窗口与前缀和是解决字符串匹配与子数组问题的核心算法。滑动窗口通过维护固定窗口实现高效字符统计适用于定长匹配场景前缀和 哈希表则解决了含负数的子数组和问题是不定长区间问题的通用方案。掌握这两种算法的核心原理与实现细节能大幅提升刷题效率与面试竞争力。后续可进一步学习滑动窗口的可变长度实现、二维前缀和等扩展应用深入理解算法思想的本质。
