题目1：无重复字符的最长子串（LeetCode 3）
问题描述
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
示例：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，长度为 3。
解题思路
核心思想： 滑动窗口（双指针）+ HashSet
-
使用 left 和 right 两个指针维护一个窗口
-
right 不断右移，将字符加入窗口
-
如果遇到重复字符，移动 left 指针，从窗口中移除字符，直到没有重复
-
每次更新最大长度
Java代码（带详细注释）
import java.util.HashSet;
import java.util.Set;
/**
* LeetCode 3. 无重复字符的最长子串
* 难度：中等
* 给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。
*/
public class LongestSubstringWithoutRepeating {
public int lengthOfLongestSubstring(String s) {
// 边界检查
if (s == null || s.length() == 0) {
return 0;
}
// 使用 HashSet 存储窗口中的字符，用于快速判断是否重复
Set<Character> set = new HashSet<>();
int left = 0; // 左指针
int maxLength = 0; // 最大长度
// 右指针不断右移
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果当前字符已经在窗口中，移动左指针直到没有重复
while (set.contains(c)) {
set.remove(s.charAt(left));
left++;
}
// 将当前字符加入窗口
set.add(c);
// 更新最大长度：当前窗口大小 = right – left + 1
maxLength = Math.max(maxLength, right – left + 1);
}
return maxLength;
}
}
流程图（Mermaid）
执行过程示例：
s = "abcabcbb"
Step 1: right=0, c='a' → set空 → 加入'a' → set=[a], max=1
Step 2: right=1, c='b' → set无'b' → 加入 → set=[a,b], max=2
Step 3: right=2, c='c' → set无'c' → 加入 → set=[a,b,c], max=3
Step 4: right=3, c='a' → set有'a' → 移除s[0]='a', left=1
→ set有'a'? 移除s[1]='b', left=2
→ set有'a'? 否 → 加入'a' → set=[c,a], max=3
Step 5: right=4, c='b' → set有'b'? 否 → 加入 → set=[c,a,b], max=3
Step 6: right=5, c='c' → set有'c'? 是 → 移除s[2]='c', left=3
→ set有'c'? 否 → 加入'c' → set=[a,b,c], max=3
Step 7: right=6, c='b' → set有'b'? 是 → 移除s[3]='a', left=4
→ set有'b'? 是 → 移除s[4]='b', left=5
→ set有'b'? 否 → 加入'b' → set=[c,b], max=3
Step 8: right=7, c='b' → set有'b'? 是 → 移除s[5]='c', left=6
→ set有'b'? 否 → 加入'b' → set=[b], max=3
最终结果: 3
题目2：找到所有字母异位词（LeetCode 438）
问题描述
给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。
示例：
输入: s = "cbaebabacd", p = "abc"
输出: [0, 6]
解释:
起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。
解题思路
核心思想： 滑动窗口 + 字符计数数组
-
使用长度为26的数组记录 p 中每个字符的出现次数
-
在 s 上维护一个固定大小的窗口（窗口大小 = p.length()）
-
每次移动窗口，更新字符计数，比较是否与 p 的计数相同
Java代码（带详细注释）
import java.util.ArrayList;
import java.util.List;
/**
* LeetCode 438. 找到所有字母异位词
* 难度：中等
* 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串。
*/
public class FindAllAnagrams {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
// 边界检查
if (s == null || p == null || s.length() < p.length()) {
return result;
}
int sLen = s.length();
int pLen = p.length();
// 使用两个数组统计字符出现次数（只有26个小写字母）
int[] pCount = new int[26]; // p 的字符计数
int[] windowCount = new int[26]; // 当前窗口的字符计数
// 1. 统计 p 中每个字符的出现次数
for (char c : p.toCharArray()) {
pCount[c – 'a']++;
}
// 2. 初始化第一个窗口
for (int i = 0; i < pLen; i++) {
windowCount[s.charAt(i) – 'a']++;
}
// 3. 检查第一个窗口是否是异位词
if (Arrays.equals(pCount, windowCount)) {
result.add(0);
}
// 4. 滑动窗口：从索引 pLen 开始
for (int i = pLen; i < sLen; i++) {
// 窗口右移：添加新字符
windowCount[s.charAt(i) – 'a']++;
// 窗口右移：移除旧字符
windowCount[s.charAt(i – pLen) – 'a']–;
// 检查当前窗口是否是异位词
if (Arrays.equals(pCount, windowCount)) {
result.add(i – pLen + 1); // 窗口起始索引
}
}
return result;
}
/**
* 辅助方法：比较两个计数数组是否相同
*/
private boolean isSame(int[] arr1, int[] arr2) {
for (int i = 0; i < 26; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
}
流程图（Mermaid）
执行过程示例：
s = "cbaebabacd", p = "abc"
pCount: a=1, b=1, c=1
初始化窗口 [0,2]: "cba"
windowCount: a=1, b=1, c=1 → 匹配 → result=[0]
滑动到 [1,3]: "bae"
windowCount: a=1, b=1, e=1 → 不匹配
滑动到 [2,4]: "aeb"
windowCount: a=1, b=1, e=1 → 不匹配
滑动到 [3,5]: "eba"
windowCount: a=1, b=1, e=1 → 不匹配
滑动到 [4,6]: "bab"
题目3：和为K的子数组（LeetCode 560）
问题描述
给定一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例：
输入: nums = [1, 1, 1], k = 2
输出: 2
解释: [1,1] 和 [1,1]（两个不同的子数组）
解题思路
核心思想： 前缀和 + HashMap
-
prefixSum 表示从 0 到当前位置的和
-
如果 prefixSum – k 之前出现过，说明存在子数组和为 k
-
使用 HashMap 存储每个前缀和出现的次数
关键公式：
子数组和 = prefixSum[i] – prefixSum[j-1] = k
等价于：prefixSum[j-1] = prefixSum[i] – k
Java代码（带详细注释）
import java.util.HashMap;
import java.util.Map;
/**
* LeetCode 560. 和为K的子数组
* 难度：中等
* 给定一个整数数组和一个整数 k，统计和为 k 的连续子数组的个数。
*/
public class SubarraySumEqualsK {
public int subarraySum(int[] nums, int k) {
// 边界检查
if (nums == null || nums.length == 0) {
return 0;
}
// key: 前缀和, value: 该前缀和出现的次数
Map<Integer, Integer> prefixSumMap = new HashMap<>();
// 重要！初始化：前缀和为0出现1次
// 这是为了处理从数组开头到当前位置的子数组
prefixSumMap.put(0, 1);
int prefixSum = 0; // 当前前缀和
int count = 0; // 满足条件的子数组个数
// 遍历数组
for (int num : nums) {
// 更新前缀和
prefixSum += num;
// 检查 prefixSum – k 是否出现过
// 如果出现过，说明存在子数组和为 k
int target = prefixSum – k;
if (prefixSumMap.containsKey(target)) {
count += prefixSumMap.get(target);
}
// 记录当前前缀和出现的次数
prefixSumMap.put(prefixSum,
prefixSumMap.getOrDefault(prefixSum, 0) + 1);
}
return count;
}
}
流程图（Mermaid）
执行过程示例：
nums = [1, 1, 1], k = 2
初始: map = {0:1}, prefixSum=0, count=0
遍历:
Step 1: num=1
prefixSum = 0+1 = 1
target = 1-2 = -1
map有-1吗? 没有
map.put(1, 1) → map = {0:1, 1:1}
Step 2: num=1
prefixSum = 1+1 = 2
target = 2-2 = 0
map有0吗? 有！count += map.get(0)=1 → count=1
map.put(2, 1) → map = {0:1, 1:1, 2:1}
// 子数组 [1,1] (索引0-1) ✓
Step 3: num=1
prefixSum = 2+1 = 3
target = 3-2 = 1
map有1吗? 有！count += map.get(1)=1 → count=2
map.put(3, 1) → map = {0:1, 1:1, 2:1, 3:1}
// 子数组 [1,1] (索引1-2) ✓
最终结果: 2
更复杂的例子：
nums = [1, 2, 3], k = 3
初始: map = {0:1}, prefixSum=0, count=0
Step 1: num=1
prefixSum=1, target=-2 → 不匹配
map = {0:1, 1:1}
Step 2: num=2
prefixSum=3, target=0 → map有0! count=1
子数组: [1,2] ✓
map = {0:1, 1:1, 3:1}
Step 3: num=3
prefixSum=6, target=3 → map有3! count=2
子数组: [3] ✓
map = {0:1, 1:1, 3:1, 6:1}
最终结果: 2
