🧮 Week 1 · Day 3 — LeetCode Hot 100 学习笔记
📘 1. 无重复字符的最长子串（Longest Substring Without Repeating Characters）
题目描述：
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
示例：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
🔹 解法：滑动窗口 + 哈希表（双指针）
思路解析：
-
使用两个指针
left和right表示当前子串的窗口； -
使用
cnt（哈希表）记录窗口中每个字符的出现次数； -
每次右移
right指针时，将当前字符计入哈希表； -
如果发现重复字符（
cnt[x] > 1），则不断右移left，直到窗口中没有重复字符； -
每次更新
ans = max(ans, right - left + 1)。
实现代码：
from collections import defaultdict
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
cnt = defaultdict(int)
left = 0
for right, x in enumerate(s):
cnt[x] += 1
while cnt[x] > 1:
cnt[s[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
时间复杂度： O(n)
空间复杂度： O(字符集大小)
📗 2. 找到字符串中所有字母异位词（Find All Anagrams in a String）
🔗 LeetCode 438. Find All Anagrams in a String
题目描述：
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。
示例：
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引 0 的子串 "cba" 是 "abc" 的异位词；
起始索引 6 的子串 "bac" 也是 "abc" 的异位词。
🔹 解法：定长滑动窗口 + 哈希表（Counter）
思路解析：
-
用
Counter(p)统计目标字符串中各字符出现次数； -
在
s上维护一个长度为len(p)的滑动窗口； -
每次右移窗口时：
-
将新字符加入计数；
-
移除窗口左侧多余字符；
-
-
若窗口内字符频次与
p的频次相同，则记录当前起始索引。
实现代码：
from collections import Counter
from typing import List
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ans = []
cnt_p = Counter(p)
cnt_s = Counter()
for right, c in enumerate(s):
cnt_s[c] += 1
left = right - len(p) + 1
if left < 0:
continue
if cnt_s == cnt_p:
ans.append(left)
out = s[left]
cnt_s[out] -= 1
if cnt_s[out] == 0:
del cnt_s[out]
return ans
时间复杂度： O(n)
空间复杂度： O(k)
📙 3. 和为 K 的子数组（Subarray Sum Equals K）
🔗 LeetCode 560. Subarray Sum Equals K
题目描述：
给定一个整数数组 nums 和一个整数 k，请你统计并返回 该数组中和为 k 的子数组的个数。
子数组是数组中元素的连续非空序列。
🔹 解法：前缀和 + 哈希表
核心思路：
-
设
prefix[j]表示前j个元素的前缀和； -
若存在
i < j，使得prefix[j] - prefix[i] = k，
则[i, j-1]之间的子数组和为k； -
用哈希表
cnt记录 每个前缀和出现的次数； -
对于当前前缀和
s，检查是否存在s - k。
实现代码：
from collections import defaultdict
from typing import List
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
s = 0
cnt = defaultdict(int)
cnt[0] = 1
ans = 0
for x in nums:
s += x
ans += cnt[s - k]
cnt[s] += 1
return ans
时间复杂度： O(n)
空间复杂度： O(n)