hot100刷题第1-9题，三个专题哈希，双指针，滑动窗口

本文主要是介绍hot100刷题第1-9题，三个专题哈希，双指针，滑动窗口，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求满足条件的子数组，一般是前缀和、滑动窗口，经常结合哈希表；

区间操作元素，一般是前缀和、差分数组

数组有序，更大概率会用到二分搜索

目前已经掌握一些基本套路，重零刷起leetcode hot 100， 套路题按套路来，非套路题适当参考gpt解法。

一、梦开始的地方， 两数之和

 class Solution:#注意要返回的是数组下标def twoSum(self, nums: List[int], target: int) -> List[int]:val2index = {}for i in range(len(nums)):diff = target - nums[i]if diff in val2index:return [val2index[diff], i]val2index[nums[i]] = i 

二、 字母异位词分组

键的可哈希性（哈希表键必须是不可变的类型）：

• 哈希表的键必须是 不可变对象，因为哈希表在计算键的哈希值时要求键不能变化。在 Python 中，tuple 是不可变的，因此我们在使用字符频次时，将数组转化为元组 tuple 来作为键

• 可迭代对象：可以逐个返回其元素，并可以用 for 循环进行遍历。包括列表、元组、字符串、集合、字典、生成器等。

  不可变对象：一旦创建，其内容不能被修改。包括整数、浮点数、字符串、元组、冻结集合等。

• 1. 遍历字典的键（默认行为）

  如果你直接遍历字典，默认遍历的是字典的键：

my_dict = {'a': 1, 'b': 2, 'c': 3}for key in my_dict:print(key)

本体代码采用以sorted之后的字符串作为键，因为若字符串互为异位词，他们肯定sorted之后一样

sorted() 是 Python 内置的一个函数，用于对可迭代对象（如列表、字符串、元组等）进行排序，并返回一个新的 排序后的列表。原始数据不会被修改。

在 Python 中，sorted() 函数对字符串进行排序后，返回的是一个 列表，而不是字符串。因此，如果你想将排序后的字符重新合并成一个字符串，必须使用 ''.join() 方法。 sorted()函数返回的是一个列表

class Solution:def groupAnagrams(self, strs: list[str]) -> list[list[str]]:anagrams = {}for s in strs:# 将字符串的字符排序，作为字典的键key = ''.join(sorted(s))# 将相同字母组成的字符串放到同一个组里if key in anagrams:anagrams[key].append(s)else:anagrams[key] = [s]# 返回字典中所有的值，即每组字母异位词return list(anagrams.values())

字典视图对象：提供对字典中键、值或键值对的动态视图，自动反映字典的当前状态。

转换为列表：将视图对象转换为列表可以提供对字典内容的固定快照，支持索引、排序和其他列表操作，同时也可以与旧版代码兼容。

也就是dict.values()得到的是动态试图，需要list固定为列表。

三、最长连续序列

哈希字典与哈希集合

在 Python 中，set 和 dict 都是基于哈希表实现的，它们在许多操作上的时间复杂度是相同的，但它们的用途和内部实现有所不同。以下是 set 和 dict 的时间复杂度以及它们之间的主要区别，哈希字典的键具有唯一性，哈希集合具有唯一性。

时间复杂度

set

• 查找：O(1)

  • 使用哈希表来存储元素，使得查找某个元素的时间复杂度为常数时间。

• 插入：O(1)

  • 插入一个元素也在常数时间内完成，前提是哈希表中的位置冲突很少。

• 删除：O(1)

  • 删除元素的时间复杂度为常数时间。

• 迭代：O(n)

  • 遍历集合中的所有元素的时间复杂度为线性时间，其中 n 是集合中元素的数量。

dict

• 查找：O(1)

  • 类似于 set，字典的查找操作在常数时间内完成。

• 插入：O(1)

  • 插入键值对的时间复杂度为常数时间。

• 删除：O(1)

  • 删除键值对的时间复杂度也是常数时间。

• 迭代：O(n)

  • 遍历字典中的所有键值对的时间复杂度为线性时间，其中 n 是字典中键值对的数量。

主要区别

1. 数据结构

   • set：只存储元素，不存储键值对。集合中的每个元素必须是唯一的，集合的主要操作是测试元素是否存在、添加和删除元素。
   • dict：存储键值对，每个键（key）与一个值（value）相关联。字典允许快速查找、插入和删除键值对。

2. 用途

   • set：适用于需要处理唯一元素的情况，如测试某个元素是否存在、去重操作等。
   • dict：适用于需要将键映射到值的情况，如存储和查找数据的键值对、实现字典的功能等。

3. 存储

   • set：内部存储的是集合的元素，没有与之关联的值。
   • dict：内部存储的是键值对，每个键都关联一个值。

4. 操作方法

   • set：支持 add(), remove(), discard(), pop(), clear(), 等方法来处理元素。
   • dict：支持 get(), setdefault(), pop(), popitem(), update(), clear(), 等方法来处理键值对。

字典中的键值对是无序的。虽然从 Python 3.7 开始，字典保持插入顺序，但这种顺序是实现细节，并不影响字典的核心操作。

列表各操作的时间复杂度高。 所以本文要实现O（n）的时间复杂度需要用到哈希集合这一数据结构，

在 Python 中，列表（list）是一种动态数组，提供了许多操作来管理和操作其中的元素。以下是常见列表操作的时间复杂度分析：

时间复杂度总结

操作详细说明

1. 访问元素（索引访问）：

   • 时间复杂度：O(1)
   • 说明：通过索引访问列表中的元素是常数时间操作，因为列表在内存中是连续存储的。

2. 添加元素（末尾）：

   • 时间复杂度：O(1) 均摊
   • 说明：在列表的末尾添加元素通常是常数时间操作。但如果列表的容量需要扩展（例如，在数组容量不足时），这可能会导致重新分配内存，导致时间复杂度上升。总体来说，均摊时间复杂度为 O(1)。

3. 插入元素（任意位置）：

   • 时间复杂度：O(n)
   • 说明：在列表中的任意位置插入元素需要将插入位置后的所有元素向后移动，因此时间复杂度为 O(n)。

4. 删除元素（任意位置）：

   • 时间复杂度：O(n)
   • 说明：在列表中删除元素也需要移动删除位置后的所有元素，因此时间复杂度为 O(n)。

5. 查找元素：

   • 时间复杂度：O(n)
   • 说明：查找元素需要遍历整个列表以查找匹配的元素，时间复杂度为 O(n)。

6. 删除元素（值匹配）：

   • 时间复杂度：O(n)
   • 说明：删除指定值的元素需要首先查找元素的位置（O(n)），然后删除它（O(n)）。总体时间复杂度为 O(n)。

7. 遍历（迭代）：

   • 时间复杂度：O(n)
   • 说明：遍历列表中的所有元素需要访问每个元素一次，因此时间复杂度为 O(n)。

8. 排序：

   • 时间复杂度：O(n log n)
   • 说明：Python 中的列表排序（list.sort()）使用 Timsort 算法，时间复杂度为 O(n log n)。

9. 反转：

   • 时间复杂度：O(n)
   • 说明：反转列表中的元素需要访问每个元素一次，因此时间复杂度为 O(n)。

class Solution:def longestConsecutive(self, nums: List[int]) -> int:set_nums = set(nums)max_length = 0 for num in set_nums:if num - 1 not in set_nums:cur_num = num cur_len = 1while cur_num + 1 in set_nums:cur_num += 1cur_len += 1max_length = max(cur_len, max_length) return max_length

算法的时间复杂度是O(n)的，每个数字最多被访问2次。

四、移动零, 梦醒，意识到需要刷题

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""#快慢指针，j在后，i在前,j用来记录放置非零元素的位置j = 0for i in range(len(nums)):if nums[i] != 0:nums[j] = nums[i]j += 1for k in range(j, len(nums)):nums[k] = 0

五、 盛最多水的容器

class Solution:def maxArea(self, height: List[int]) -> int:#写一遍暴力解法看看能否通过n =len(height)max_area = 0 for i in range(n):for j in range(i + 1, n):cur_area = min(height[i], height[j]) * (j - i)max_area = max(cur_area, max_area)return max_area 

为什么使用双指针？

为了优化暴力解法，可以采用双指针策略。使用双指针的核心思想是：

• 初始状态：将左右两个指针分别放在数组的两端，假设它们是构成容器的两条线。

• 贪心策略

  ：每次计算当前容器的容量，比较容器左右两侧的高度，移动较短的那一边的指针。因为容器的容量由短板决定，只有移动短板指针才有可能找到更大的容量。

  • 如果移动长板，水量不会增加，因为短板高度没有变，距离变小了；
  • 移动短板可能会增加高度，尽管距离缩短，但容量有可能变大。

通过不断移动指针，逐步缩小搜索范围，最终可以在 O(n)O(n)O(n) 的时间复杂度内找到最大水量。

class Solution:def maxArea(self, height: List[int]) -> int:#用到双向双指针，指针名字就用left,right命名，更明显left, right = 0, len(height) - 1res = 0 while left < right :cur_area = min(height[left], height[right]) * (right - left)res = max(res, cur_area)#想想移动指针的逻辑是什么，指针总是需要移动的,移动矮的板子才有可能获得更大的面积if height[left] < height[right]:left += 1else:right -= 1return res 

双指针算法可以优化时间复杂度，上面两问题都从暴力解法的O(N^2)降低复杂度到O（n） 双向双指针的使用条件是left < right

双向双指针不是穷举，它是一种优化暴力解法的技巧。虽然它在某种程度上仍然需要检查不同的组合，但它通过更智能的方式减少了计算量，从而使得算法的效率更高。

六、三数之和

双指针法

适用场景：一般用于处理排序数组中的问题，常用于寻找满足某些条件的数对或数组，特别是在解决与数组范围、区间、或有序性相关的问题时。

工作原理：

• 双指针通常指向数组的两端（有时也可以指向同一侧，如快慢指针问题）。
• 两个指针向中间收敛或朝一个方向移动，逐步缩小搜索范围。
• 通过比较两端的值，移动其中一个指针，直到找到目标或者条件不再满足。 主要用于线性扫描，常结合排序 操作多个指针同时移动，减少不必要的组合
• 双指针法 更适合解决多个元素之间的关系，例如查找数对、三元组等。而 二分查找 更专注于快速找到单个目标元素。两者的思路和应用场景不同，但都非常高效

双指针法的判断条件是while left < right 与二分查找习惯使用的闭区间具有明显不同，

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:res = []nums.sort()#固定i，之后双指针查找另一对数，使三者和为零for i in range(0, len(nums) - 2):if i > 0 and nums[i] == nums[i - 1]:continue left, right = i + 1, len(nums) - 1#双指针重要逻辑，要条件反射立马衔接上，#命名完左右指针之后立马写while left < right 双指针逻辑要包含整个移动过程while left < right:total = nums[i] + nums[left] + nums[right] if total < 0:left += 1elif total > 0:right -= 1else: res.append([nums[i], nums[left], nums[right]])#这一组已经成功，跳过重复的while left < right and nums[left] == nums[left + 1]:left += 1while left < right and nums[right] == nums[right - 1]:right -= 1left += 1right -= 1return res 

思路

1. 排序数组：首先将数组排序，这样可以更方便地找到三元组，并且可以在后续的步骤中跳过重复的元素。
2. 固定一个数，使用双指针查找另一对数：
   • 选择一个数作为固定数（nums[i]），然后在剩下的数组中使用双指针技术找到两个数，使得这三个数的和为零。
   • 将双指针从剩余的数组两端开始向中间移动，通过调整指针的位置找到满足条件的数对。
3. 跳过重复的数：
   • 在选择固定数或移动双指针时，跳过重复的元素，以避免出现重复的三元组。

本题中，两次跳过重复数的操作逻辑有所不同

跳过 nums[i] 是为了避免在不同循环中的 i 选择时，出现相同的第一个数，避免整体三元组的重复。

跳过 nums[left] 和 nums[right] 是为了避免在已经找到一个三元组后，由于 left 和 right 的相同值导致的数对重复。

七、接雨水

class Solution:def trap(self, height: List[int]) -> int:n = len(height) water = 0for i in range(1, n - 1):#最左和最右是不可能积水的left_max = max(height[:i])right_max = max(height[i + 1:])cur_water = min(left_max, right_max) - height[i]if cur_water > 0:water += cur_water return water

动态规划的关键特征：

1. 子问题重叠

   ：

   • 对于每一个柱子 i，我们需要知道它左边的最高柱子 left_max[i] 和右边的最高柱子 right_max[i]。在暴力方法中，max(height[:i]) 和 max(height[i+1:]) 都是需要重复计算的子问题。每次计算时都需要扫描一遍前面或后面的子数组，这就是子问题的重叠。

2. 最优子结构

   ：

   • 为了计算某个柱子 i 上方的积水量，我们只需要知道左边和右边的最高柱子，水量由它们的最小值决定。计算某个柱子积水量的最优解可以通过它左边和右边的局部信息得到，不需要考虑其他柱子。

方法二、用空间换时间。存储最高值 通过动态规划避免重复计算 预计算的方法

为了优化暴力解法的 O(n²) 时间复杂度，我们使用 两个数组 分别保存左边最高值和右边最高值的计算结果。这样，我们可以通过一次遍历提前计算出左边和右边的最大高度，接着在 O(n) 时间内完成接水量的计算。我们不再需要每次重新扫描子数组，这就是动态规划的应用场景。

用一个数组 left_max[]，其中 left_max[i] 存储柱子 i 左边（包括自己）的最高柱子。

用另一个数组 right_max[]，其中 right_max[i] 存储柱子 i 右边（包括自己）的最高柱子。 动态规划！！用空间换时间

class Solution:def trap(self, height: List[int]) -> int:n = len(height)left_max = [0] * n right_max = [0] * n #记录左侧最高值，包含本身left_max[0] = height[0]for i in range(1, n):left_max[i] = max(left_max[i - 1], height[i])#记录右侧最高值，包含本身right_max[n - 1] = height[n - 1]for i in range(n - 2, -1, -1):right_max[i] = max(right_max[i + 1], height[i])water = 0 for i in range(1, n - 1):cur_water = min(left_max[i], right_max[i]) - height[i]if cur_water > 0 :water += cur_water return water

方法三、利用双指针算法，边走变算，当前点的水量由两边低的一侧决定。

关键点解释：

1. 双指针移动策略

   ：

   • 由于积水量由两侧的较小值决定，因此我们每次移动较低的一侧指针，从而更新积水量。

2. 动态维护 left_max 和 right_max

   ：

   • 随着指针移动，动态更新左右两边的最高值，用以计算积水量。

时间复杂度：O(n)，因为我们只扫描一次数组。 空间复杂度：O(1)，只使用了常数额外空间。

class Solution:def trap(self, height: List[int]) -> int:left, right = 0, len(height) - 1total = 0 l_max, r_max = 0, 0while left < right:#依次计算左边最高值和右边最高值l_max = max(l_max, height[left])r_max = max(r_max, height[right])#水量由矮的边决定if l_max < r_max:total += l_max - height[left]left += 1else:total += r_max - height[right]right -= 1return total

八、无重复字符的最长子串

1. 什么时候应该扩大窗口？

我们需要扩大窗口的情况是，当当前窗口内的字符没有重复时。具体而言，当我们处理新的字符时，如果该字符不在当前的滑动窗口中（即窗口内没有出现过该字符），我们就可以安全地将窗口右边界扩大，即右移右边界。

2. 什么时候应该缩小窗口？

如果当前窗口内出现了重复字符，则需要缩小窗口。具体做法是从窗口的左边界开始逐步右移，直到窗口内没有重复字符为止。通常这意味着需要将左边界移到上次出现重复字符的位置之后。缩小窗口要缩小直到没有重复字符为止。

3. 什么时候应该更新答案？

答案应该在每次扩大窗口（即窗口内没有重复字符时）时更新。每当窗口右边界扩大时，我们计算当前窗口的长度，并与之前保存的最长无重复子串长度进行比较。如果当前窗口长度更大，则更新最长子串的长度。

滑动窗口的实用意义在于它能通过局部调整和动态维护解决需要遍历连续区间的问题，以极高的效率处理大规模数据。同时它广泛应用于字符串、数组等一维数据结构的区间问题，具有极高的实践价值

提升效率： 滑动窗口的主要优势在于避免重复计算，提高算法效率。例如，在求解子串或子数组问题时，传统方法可能会对所有子区间进行枚举，这通常会带来 O(n²) 的复杂度。而滑动窗口算法通过智能地移动左右边界，使得每个元素仅被访问一次，将复杂度降为 O(n)。这在处理大规模数据时显得尤为重要。

优化内存使用： 滑动窗口通过动态维护一个子区间，只需要存储当前窗口中的内容，不需要额外保存所有的子数组或子串。这种特性使得滑动窗口在内存消耗上非常高效。对于需要处理海量数据的问题，内存占用是一个重要的考量，滑动窗口可以通过限制窗口大小避免内存爆炸

滑动窗口模板，这种题目还是依照模板来写，更有章法 先思考什么时候加入，加入的操作是什么， 再思考什么时候缩小窗口，缩小的操作是什么。 再思考什么时候应该更新答案

# 滑动窗口算法伪码框架
def slidingWindow(s: str):# 用合适的数据结构记录窗口中的数据，根据具体场景变通# 比如说，我想记录窗口中元素出现的次数，就用 map# 如果我想记录窗口中的元素和，就可以只用一个 intwindow = ...left, right = 0, 0while right < len(s):# c 是将移入窗口的字符c = s[right]window.add(c)# 增大窗口right += 1# 进行窗口内数据的一系列更新...# *** debug 输出的位置 ***# 注意在最终的解法代码中不要 print# 因为 IO 操作很耗时，可能导致超时# print(f"window: [{left}, {right})")# ***********************# 判断左侧窗口是否要收缩while left < right and window needs shrink:# d 是将移出窗口的字符d = s[left]window.remove(d)# 缩小窗口left += 1# 进行窗口内数据的一系列更新...

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:window = {}left, right = 0, 0 res=  0 #进行滑动窗口，右窗口的临界，每一题都一致。while right < len(s):#进入窗口的元素加载，c = s[right]right += 1#进入窗口数据的更新window[c] = window.get(c, 0) + 1#window[c] 是计数器，计数器说明存在重复字符,用while，因为可能连续多次收缩while window[c] > 1:d = s[left]left += 1window[d] -= 1#这一层判断完之后window里面没有重复字符了res = max(res, right - left )return res 

九、找到字符串中所有字母异位词

1. 什么时候应该扩大窗口？

首先初始化一个大小为 p 长度的窗口，开始在 s 上滑动。每次右移右边界时，操作：将新加入的字符频率计入当前窗口的字符统计中。

扩大窗口的条件是：每次右移右边界 right，直到窗口大小等于 p。从 s 的开头开始遍历，当窗口大小小于 p 的时候，始终右移来扩大窗口。

2. 什么时候应该缩小窗口？

当窗口大小超过 p 的长度时，我们需要通过移动左边界 left 来缩小窗口。具体来说，当 right - left 的窗口长度大于 p 的长度时，左移 left 使得窗口保持为 p 的长度，并更新窗口内的字符频率。

3. 什么时候应该更新答案？

每当窗口的大小等于 p 且窗口内的字符频率与 p 的字符频率相同时，就说明当前窗口内的子串是 p 的一个异位词。此时更新结果，记录 left 作为子串的起始索引。

python中defaultdict。在 defaultdict 中，默认值不是固定为 0，而是取决于你传递给 defaultdict 的默认工厂函数。如果你传入的是 int，默认值会是 0，因为 int() 的默认返回值是 0。 与普通字典的区别就是普通字典中如果键不存在，会报key error。 而defaultdict会默认给不存在的键赋值为0

若不采用defaultdict，则同等代码为

need = {}
for c in range(s):need[c] = need.get(c, 0) + 1等价于
need = defaultdict(int)
for c in range(s):need[c] += 1

使用 valid 变量的主要目的是提高效率，通过减少每次窗口移动时的检查复杂度。它使得我们在窗口大小满足条件时，仅通过一个简单的检查 (valid 是否等于 need 中不同字符的数量) 来确认是否找到了一个异位词子串。这种方法简化了逻辑，并提升了算法的效率 利用valid判断何时全部验证完了

在这个算法中，need 和 window 是两个 defaultdict 用于存储字符的频率信息，它们分别具有以下含义：

1. need

• 含义：need 是一个 defaultdict(int)，用于记录目标字符串 t 中每个字符的频率需求。它表示 t 中每个字符在异位词中的出现次数。
• 用途：在滑动窗口的过程中，need 提供了一个基准，帮助我们确定当前窗口内的字符是否符合 t 中字符的频率要求。

2. window

• 含义：window 是一个 defaultdict(int)，用于记录当前滑动窗口内每个字符的频率。它表示在窗口范围内的字符出现的实际次数。
• 用途：在滑动窗口的过程中，window 用于跟踪窗口内字符的出现次数，并与 need 中的字符频率进行比较，以检查窗口是否符合 t 中字符的频率需求

need,window用来统计频率信息。

from collections import defaultdictclass Solution:def findAnagrams(self, s: str, t: str) -> list[int]:need = defaultdict(int)window = defaultdict(int)for c in t:need[c] += 1left = 0right = 0valid = 0# 记录结果res = []while right < len(s):c = s[right]right += 1# 进行窗口内数据的一系列更新if c in need:window[c] += 1if window[c] == need[c]:valid += 1# 判断左侧窗口是否要收缩while right - left >= len(t):# 当窗口符合条件时，把起始索引加入 resif valid == len(need):res.append(left)d = s[left]left += 1# 进行窗口内数据的一系列更新if d in need:if window[d] == need[d]:valid -= 1window[d] -= 1return res

这篇关于hot100刷题第1-9题，三个专题哈希，双指针，滑动窗口的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！