跳到主要内容 LeetCode 热题 100 Python 算法题解：哈希、双指针、滑动窗口及子串 | 极客日志
Python 算法
LeetCode 热题 100 Python 算法题解：哈希、双指针、滑动窗口及子串 LeetCode 热题 100 中的 Python 算法题解，涵盖哈希表、双指针、滑动窗口及子串相关经典问题。内容包括两数之和、字母异位词分组、最长连续序列、移动零、盛最多水的容器、三数之和、接雨水、无重复字符的最长子串、找到字符串中所有字母异位词、和为 K 的子数组、滑动窗口最大值及最小覆盖子串等题目的解题思路与代码实现。重点讲解了利用哈希表优化查找、双指针处理数组操作、滑动窗口解决子串子数组问题的核心逻辑。
人间过客 发布于 2026/3/30 更新于 2026/4/13 哈希
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
**输入：**nums = [2,7,11,15], target = 9 输出： [0,1] **解释：**因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
**输入：**nums = [3,2,4] 输出： [1,2]
示例 3：
**输入：**nums = [3,3] 输出： [0,1]
提示：
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9只会存在一个有效答案
class Solution :
def twoSum (self, nums: List [int ], target: int ) -> List [int ]:
for i in range (len (nums)):
for n in range (i+1 , len (nums)):
if target == nums[i] + nums[n]:
return [i, n]
这是最简单的做法，即直接遍历整个列表，从第一个值开始遍历，如果从当前位置到最后位置中有和当前位置值相加为目标值的即返回这两个位置。
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
curl 转代码 解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate"，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i] 仅包含小写字母 class Solution :
def groupAnagrams (self, strs: List [str ] ) -> List [List [str ]]:
d = defaultdict(list )
for s in strs:
sorted_s = '' .join(sorted (s))
d[sorted_s].append(s)
return list (d.values())
这个稍微难一些，并且会用到新东西。下面一行一行拆解：
d=defaultdict(list) 这个是当你访问一个不存在的键时，它不会报错，而是会自动创建这个键，并把它的值设为一个空列表 []。这样我们就不用写 if 语句判断键是否存在了。
sorted_s = ''.join(sorted(s)) 对于每个字符串 s，例如第一个字符串 "eat"：
sorted(s)会将字符串拆成字符并排序，得到 ['a', 'e', 't']。''.join(...)再将这个字符列表拼接回一个字符串 "aet"。这个 "aet"就是这组字母异位词的唯一标识（钥匙） 。无论原字符串是 "eat"、"tea"还是 "ate"，它们排序后都会得到相同的 "aet"。 分组归位 (d[sorted_s].append(s))
这是最精妙的一步。我们通过上一步生成的密钥 sorted_s来操作字典 d。
如果是第一次遇到 "aet"这个键，d会自动创建 "aet"键，并将其值初始化为空列表 []，然后立刻将原字符串 "eat"添加进去。
当处理到 "tea"时，排序后密钥同样是 "aet"。此时 d["aet"]这个键已经存在，其值是 ["eat"]，我们直接调用 append("tea")，列表就变成了 ["eat", "tea"]。
处理完所有字符串后，字典 d的内容类似这样：{"aet": ["eat", "tea"], "ant": ["tan"]}。
输出结果 (return list(d.values()))
最后，我们不需要关心键是什么，只需要所有的分组结果。d.values()返回的就是字典中所有值的视图，即 [["eat", "tea"], ["tan"]]。用 list()将其转换为列表并返回，就得到了最终答案。
给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
**输入：**nums = [100,4,200,1,3,2] **输出：**4 **解释：**最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
**输入：**nums = [0,3,7,2,5,8,4,6,0,1] **输出：**9
**输入：**nums = [1,0,1,2] **输出：**3
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9 class Solution :
def longestConsecutive (self, nums: List [int ] ) -> int :
st = set (nums)
ans = 0
for x in st:
if x - 1 in st:
continue
y = x + 1
while y in st:
y += 1
ans = max (ans, y - x)
return ans
一看到这个题第一反应是排序，但是题目说时间复杂度为 O(n)，但是排序为 O(nlogn)，所以考虑哈希表。
首先把 nums 转为哈希集合，这样判断数字在 nums 里只需要 O(1)。然后遍历哈希集合，如果 x-1 在集合里，那么 x 可以直接跳过，因为不可能比从 x-1 更长了。最后设置 y 为 x+1，如果 y 在集合里，则 y 再加一，最后 ans 为现有最大 ans 和当前 y-x 中的最大值。
**输入：**nums = [100,4,200,1,3,2] **输出：**4 **解释：**最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
这个就是 x=1，y=2,3,4 然后最后一次 4 也在集合中 y 会再加一，这个时候 y=5，所以 5-1=4。
双指针 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
1 <= nums.length <= 10^4-2^31 <= nums[i] <= 2^31 - 1 class Solution :
def moveZeroes (self, nums: List [int ] ) -> None :
left = right = 0
n = len (nums)
while right < n:
if nums[right] != 0 :
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
这一题很巧妙的点在于用双指针可以互换数组里面数字的位置，可以自己画一下图理解一下。
给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
输入： [1,8,6,2,5,4,8,3,7] **输出：**49 **解释：**图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
**输入：**height = [1,1] **输出：**1
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4 class Solution :
def maxArea (self, height: List [int ] ) -> int :
left, right = 0 , len (height) - 1
maxar = 0
while left < right:
maxar = max (maxar, (right - left) * min (height[left], height[right]))
if height[left] < height[right]:
left += 1
else :
right -= 1
return maxar
第一反应是两个 for 循环，但是时间复杂度过不去，所以用双指针。
首先在数组首尾设立双指针，这个时候最大面积等于指针指向位置中较小的数乘以指针之间的距离。
首先置为首尾，这时候只能移动值较小的指针。
可以模拟一下，如果移动较大值的指针，那么指针间的距离减小了，指针指向位置中较小的数只可能不变或者减小，这样面积一定减小。
反之，我们移动较小值的指针，面积则可能增大。
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
**输入：**nums = [-1,0,1,2,-1,-4] 输出： [[-1,-1,2],[-1,0,1]] **解释：**nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0。nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0。nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0。不同的三元组是 [-1,0,1] 和 [-1,-1,2]。注意，输出的顺序和三元组的顺序并不重要。
**输入：**nums = [0,1,1] 输出： [] **解释：**唯一可能的三元组和不为 0。
**输入：**nums = [0,0,0] 输出： [[0,0,0]] **解释：**唯一可能的三元组和为 0。
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5 class Solution :
def threeSum (self, nums: List [int ] ) -> List [List [int ]]:
nums.sort()
res, k = [], 0
for k in range (0 , len (nums) - 2 ):
if nums[k] > 0 :
break
if k > 0 and nums[k] == nums[k - 1 ]:
continue
i, j = k + 1 , len (nums) - 1
while i < j:
s = nums[k] + nums[i] + nums[j]
if s < 0 :
i += 1
while i < j and nums[i] == nums[i - 1 ]:
i += 1
elif s > 0 :
j -= 1
while i < j and nums[j] == nums[j + 1 ]:
j -= 1
else :
res.append([nums[k], nums[i], nums[j]])
i += 1
j -= 1
while i < j and nums[i] == nums[i - 1 ]:
i += 1
while i < j and nums[j] == nums[j + 1 ]:
j -= 1
return res
首先可以想到三数之和为 0，我们只需要先用指针 k 固定住数组中的一个数，然后用双指针 i，j 分别从 k 相邻的右边的数和最右边的数一个向后一个向前去遍历所有右边的数，只要三个相加为零就放到新的数组里面去。
当 nums[k]>0 的时候直接 break，因为这个时候 nums[j] >= nums[i] >= nums[k] > 0，三数之和不可能等于 0 了；
如果 k>0 并且 nums[k]==nums[k-1]，此时可以直接跳过当前数，因为之前的 k-1 已经把所有三数之和为 0 的数组放进去了，k 只会导致重复值；
然后让 ij 分散在 k 右边数的两端，当 i<j 时，s 等于三个指针指向的三数之和，如果 s<0 那么 i 往右移，并且跳过重复值，s>0 则 j 往左移并且跳过重复值，如果 s=0，那么把当前数值放入数组中，在 i 往右移 j 往左移的同时跳过重复值；
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
**输入：**height = [0,1,0,2,1,0,1,3,2,1,2,1] **输出：**6 **解释：**上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
**输入：**height = [4,2,0,3,2,5] **输出：**9
n == height.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5 class Solution :
def trap (self, height: List [int ] ) -> int :
n = len (height)
res = 0
left, right = 0 , n - 1
leftmax, rightmax = height[left], height[right]
left += 1
right -= 1
while left <= right:
leftmax = max (leftmax, height[left])
rightmax = max (rightmax, height[right])
if leftmax < rightmax:
res += leftmax - height[left]
left += 1
else :
res += rightmax - height[right]
right -= 1
return res
首先定义双指针 left 和 right 分别在 height 数组的最左端和最右端，当前的指针遍历过的最大值置为 leftmax 和 rightmax，最开始是等于左右俩边的俩数值的。
因为当前最左端和最右端是不可能装水的，所以 left 右移，right 左移。
当 left 小于等于 right 时，leftmax 等于 leftmax 与当前 height[left] 的最大值，rightmax 同理。
此时，如果 leftmax 小于 rightmax，说明左指针的右边一定有一个数值大于左指针左边的所有数值，那么决定当前列能装多少水的一定在左边（水桶的短板效应），所以当前列能装的水的容量就等于左边最大数值减去当前列的数值，然后 left 指针右移。
同理，如果 leftmax 大于等于 rightmax，那么当前列所能装的水等于右边最大数值减去当前列数值，right 指针左移。
还看到一个很有意思的解法，按行遍历当前行能装多少容量的水：
也就是从第一行开始遍历，当前行为 i，从左到右开始遍历墙的高度，如果高度大于等于 i，说明右边有装下水的能力，开始更新以当前墙作为左墙的当前容量，从此往后，如果高度小于 i，当前容量 +1，如果大于等于 i，把当前容量加入到总容量里去，当前容量置 0，一直重复。
其实也就是说当前小于 i 并且俩边有高度大于 i 的墙则容量 +1。（看文字有点难理解，自己拿数组推一下很简单）
滑动窗口 给定一个字符串 s，请你找出其中不含有重复字符的 最长 子串 的长度。
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个*子序列，*不是子串。
0 <= s.length <= 5 * 10^4s 由英文字母、数字、符号和空格组成 class Solution :
def lengthOfLongestSubstring (self, s: str ) -> int :
dic, res, i = {}, 0 , -1
for j in range (len (s)):
if s[j] in dic:
i = max (dic[s[j]], i)
dic[s[j]] = j
res = max (res, j - i)
return res
指针 j 遍历 s，哈希表 dic 统计字符 s[j] 最后一次出现的索引。左指针 i 初始值为 -1，也就是 j-i 就是当前不重复字符串的最大长度。
如果指针 j 当前指向的字母已经在哈希表里，那么更新 i 为哈希表中此字母的值与 i 之间的最大值，这里注意此时哈希表里这个字母的值还是上一次字母出现的位置。
在上述操作结束后再更新哈希表里当前字母出现的最后位置。
最大长度等于之前的最大长度与当下 j-i 也就是不重复字符串长度的最大值。
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
1 <= s.length, p.length <= 3 * 10^4s 和 p 仅包含小写字母 class Solution :
def findAnagrams (self, s: str , p: str ) -> List [int ]:
m, n, res = len (s), len (p), []
if n > m:
return res
s_cnt = [0 ] * 26
p_cnt = [0 ] * 26
for i in range (n):
s_cnt[ord (s[i]) - ord ('a' )] += 1
p_cnt[ord (p[i]) - ord ('a' )] += 1
if s_cnt == p_cnt:
res.append(0 )
for i in range (n, m):
s_cnt[ord (s[i - n]) - ord ('a' )] -= 1
s_cnt[ord (s[i]) - ord ('a' )] += 1
if s_cnt == p_cnt:
res.append(i - n + 1 )
return res
首先定义 m，n 为 s，p 的长度，res 记录子串的起始索引。
然后创建初始值为 0 的俩个长度为 26 的数组，用来表示 26 个字母出现次数。
一个数组用来统计 p 中字母出现的次数，另一个统计滑动窗口里字母出现次数。数组相等就输出滑动窗口左端位置。
子串 给你一个整数数组 nums 和一个整数 k，请你统计并返回 该数组中和为 k 的子数组的个数 。
**输入：**nums = [1,1,1], k = 2 **输出：**2
**输入：**nums = [1,2,3], k = 3 **输出：**2
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7 class Solution :
def subarraySum (self, nums: List [int ], k: int ) -> int :
res = 0
n = len (nums)
for i in range (n):
for j in range (i, n):
if sum (nums[i:j+1 ]) == k:
res += 1
return res
class Solution :
def subarraySum (self, nums: List [int ], k: int ) -> int :
res = 0
n = len (nums)
presums = defaultdict(int )
presums[0 ] = 1
presum = 0
for i in range (n):
presum += nums[i]
res += presums[presum - k]
presums[presum] += 1
return res
首先创建默认值为 0 的哈希表（字典）。defaultdict会在键不存在时返回指定的默认值（这里是 0），而不是引发 KeyError。
将 presums[0] 置为 1，也就是前缀和为 0 目前出现过一次。当前前缀和为 0。
遍历该数组，计算当前位置的前缀和。连续子数组的和为 k 的个数用 res 表示，此时 res 等于之前的 res 加上哈希表中当前前缀和减去 k 的位置的值，意思就是，比如 presum-k 这个前缀和如果出现了 4 次，那么 presum-（presum-k）=k 这个值就出现了四次，res+4。
然后把前缀和出现次数的哈希表中当前前缀和位置的值加一。
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
**输入：**nums = [1,3,-1,-3,5,3,6,7], k = 3 输出： [3,3,5,5,6,7] **解释：**滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
**输入：**nums = [1], k = 1 输出： [1]
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length 暴力解：但是时间复杂度是 O(k*n)，过不去时间限制
class Solution :
def maxSlidingWindow (self, nums: List [int ], k: int ) -> List [int ]:
m = len (nums)
res = []
for i in range (m - k + 1 ):
a = max (nums[i:i+k])
res += [a]
return res
class Solution :
def maxSlidingWindow (self, nums: List [int ], k: int ) -> List [int ]:
from collections import deque
m = len (nums)
dq = deque()
res = []
for i in range (m):
if dq and dq[0 ] < i - k + 1 :
dq.popleft()
while dq and nums[dq[-1 ]] < nums[i]:
dq.pop()
dq.append(i)
if i >= k - 1 :
res.append(nums[dq[0 ]])
return res
i 遍历当前数组，如果 dq 存在也就是说不是最开始遍历，且 dq 最左端队头存储的索引小于当前窗口的起始位置，说明这个数字已经不在窗口里了，要离开队伍，所以从左侧队头移除。
当 dq 存在且 dq 最右端队尾对应索引在 nums 数组里的数值小于当前的 nums[i]，那么从右侧队尾把这些小的元素移除，因为留着比当前元素小的已经没用了。
如果 i>=k-1，也就是说滑动窗口已经成立了，此时 dq[0] 就是当前窗口最大值的索引，nums[dq[0]] 就是最大值本身，把最大值加入到 res 中去。
（也就是说先确保当前的索引都是在当前滑动窗口里面的，其次，在加入新的索引的时候，保证前面索引对应的值没有比它小的值了，就能保证每一次队头索引对应的值都是最大值。）
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串 ，使得该子串包含 t 中的每一个字符（包括重复字符 ）。如果没有这样的子串，返回空字符串 ""。
**输入：**s = "ADOBECODEBANC", t = "ABC" 输出： "BANC" **解释：**最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
**输入：**s = "a", t = "a" 输出： "a" **解释：**整个字符串 s 是最小覆盖子串。
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
m == s.lengthn == t.length1 <= m, n <= 10^5s 和 t 由英文字母组成 class Solution :
def minWindow (self, s: str , t: str ) -> str :
from collections import Counter
cnt = Counter(t)
ans_l = -1
ans_r = len (s)
l = 0
count = len (cnt)
for r, c in enumerate (s):
if c in cnt:
cnt[c] -= 1
if cnt[c] == 0 :
count -= 1
while count == 0 :
if ans_r - ans_l > r - l:
ans_l, ans_r = l, r
if s[l] in cnt:
if cnt[s[l]] == 0 :
count += 1
cnt[s[l]] += 1
l += 1
return "" if ans_l == -1 else s[ans_l:ans_r+1 ]
用的是哈希表加滑动窗口，很容易理解，看一看上面的注释。
