Hot100刷题计划-Day2-滑动窗口、双指针、数组、链表、动态规划

• LeetCode Hot 100 是最常被考察的题目集合，涵盖了面试中常见的算法和数据结构问题。
• 刷 Hot100可以让你在有限的时间内集中精力解决最常考的问题。
• 不仅要写出代码，还要理解问题的本质、优化解法和复杂度分析。

滑动窗口

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。s 和 p 仅包含小写字母。

思路： 哈希表+滑动窗口。把待匹配的字符串用数组哈希化，左右指针滑动，右指针纳入元素，判断是否合法，不合法则移动左指针直到合法。若窗口合法，且长度相等，符合条件。

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:ans = []             # 存放结果答案cnt = [0] * 26       # 小写字母，26个位置存放频率for i in p:cnt[ord(i)-ord('a')] += 1   # 待匹配的字符串字符频率left = 0for right in range(len(s)):cnt[ord(s[right])-ord('a')] -= 1       # 右指针位置元素纳入窗口while cnt[ord(s[right])-ord('a')] < 0:   # 若有元素频率小于0，①不在待匹配字符串，②多次出现同一字符【都是有字符超了】cnt[ord(s[left])-ord('a')] += 1      # 将左指针对应的元素释放，频率还回去left += 1                            # 左指针右移，左指针追右指针if right - left + 1 == len(p):          # 如果长度相等，加上前面都不小于0，符合题意ans.append(left)return ans

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路： 依次纳入窗口，判断窗口中子数组是否满足target，因为要找最小长度，满足则移动左指针，更新最小长度。时间复杂度O(n)，空间O(1).

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:if sum(nums)<target: return 0  # 不存在符合条件的子数组total = 0slow = 0ans = float('inf')for fast in range(len(nums)):  total += nums[fast]         # 依次将元素纳入窗口while total >= target:        # 找最小数组，满足条件移动左指针ans = min(ans, fast-slow+1)  # 更新最小长度total -= nums[slow]slow += 1return ans

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

思路： 记录每个字符需要个数和总个数，不断扩展右边界，直到覆盖全部子串。覆盖全部子串后，再不断缩小左边界，直到找到覆盖的最小区间（其中之一）。记录区间是否需要更新，再缩小一步左边界。

class Solution:def minWindow(self, s: str, t: str) -> str:need = Counter(t)     # 统计下需要的数出现频率（更新可能出现负数）ans = (0, float('inf'))  # 元组记录起始索引和长度needcnt = len(t)      # 总需要的数left = 0for right in range(len(s)):   # 用enumerate()写会好看，扩展窗口if need[s[right]] > 0:    # 目标数，则总数减1needcnt -= 1need[s[right]] -= 1       # 字符记录到对应字典，减1if needcnt == 0:          # 满足覆盖的子数组条件while True:           # 试图移动左指针，缩小窗口if need[s[left]] == 0:breakneed[s[left]] += 1  # 不是目标数，则左移左指针left += 1if right - left < ans[1] - ans[0]: # 将所有非目标数移除，得到一个最小区间ans = (left, right)            # 如果比之前记录的小，更新need[s[left]] += 1     # 移动左指针，同时将needcnt也加个1needcnt += 1left += 1return '' if ans[1]>len(s) else s[ans[0]: ans[1]+1] # 切片用法

链表

142. 环形链表Ⅱ

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

思路： 快指针2步，慢指针1步；快慢指针环中相遇，从相遇点到环入口，和从链表到环入口距离一样。时间复杂度O(n)，空间O(1).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:fast = slow = head   # 使用快慢指针while fast and fast.next:  # 确保下一个节点存在，否则无法访问其nextslow = slow.next       # 慢指针每次走一步fast = fast.next.next  # 快指针每次走两步if fast == slow:        # 快指针在环中追到慢指针slow = head        # 重置慢指针的位置while fast != slow:slow = slow.nextfast = fast.nextreturn slow        # 慢指针再次移动的位置即为入环index

递归

78. 子集

思路： 回溯。每次进入回溯函数，先将当前集合加入结果，再遍历该层元素加入，递归回溯。主要起始位置需要变。

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:self.ans = []  # 存放结果self.backtracking(nums, 0, [])return self.ansdef backtracking(self, nums, startIndex, path):self.ans.append(path[:])  # 每次都想加入结果集for i in range(startIndex, len(nums)):path.append(nums[i])   # 往里新增该层的元素self.backtracking(nums, i+1, path) # 递归进入下一层path.pop()

回溯

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路： 不同的按键是不同的层，作为参数传递。

class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits: return []  # 处理空字符串phone_map ={'2' : 'abc','3' : 'def','4' : 'ghi','5' : 'jkl','6' : 'mno','7' : 'pqrs','8' : 'tuv','9' : 'wxyz'}self.ans = []self.backtracking(phone_map, digits, 0, [])return self.ansdef backtracking(self, phone_map, digits, startIndex, path):if startIndex == len(digits):self.ans.append(''.join(path))return letters = phone_map[digits[startIndex]]for letter in letters: path.append(letter)self.backtracking(phone_map, digits, startIndex+1, path)path.pop()

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路：

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.ans = []self.backtracking(candidates, target, [], 0)return self.ansdef backtracking(self, candidates, target, path, startIndex): if target == 0:self.ans.append(path[:])returnif target < 0:returnfor i in range(startIndex, len(candidates)):  # 为了避免顺序不同元素相同的重复，还是按顺序选path.append(candidates[i])self.backtracking(candidates, target-candidates[i], path, i) # 可以被无限选取，所以用i不用i+1path.pop()

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

思路： 如果是回文串，则加入path。path长度达到字符串长度，找到一种方案。

class Solution:def partition(self, s: str) -> List[List[str]]:self.ans = []self.backtracking(s, [], 0)return self.ansdef backtracking(self, s, path, startIndex):if startIndex >= len(s):         # 超过长度则得到一种分割方法self.ans.append(path[:])returnfor i in range(startIndex, len(s)):if s[startIndex:i+1] == s[startIndex:i+1][::-1]: # 最佳实践，判断是回文串就写入path.append(s[startIndex:i+1])self.backtracking(s, path, i+1)path.pop()