hot100内容（1、哈希--矩阵）

哈希

1、两数之和

题目描述

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target
的那两个整数，并输出它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序输出答案。

输入输出描述

输入：共两行，

• 第一行：两个整数n和target，分别表示数组nums的长度和目标值；
• 第二行：n个整数，表示数组nums的元素，数字之间以空格分隔。

输出：一行两个整数，以空格分隔，表示满足条件的两个元素的数组下标。

样例：
输入：
4 9
2 7 11 15
输出：
0 1

代码实现

defsolve(nums,target):n=len(nums)# 哈希表：key为数组元素，value为对应的下标hash_table={}foriinrange(n):complement=target-nums[i]# 检查目标差值是否已存在于哈希表中ifcomplementinhash_table:return[i,hash_table[complement]]# 将当前元素及其下标存入哈希表hash_table[nums[i]]=i# 若不存在满足条件的两个数，返回空列表return[]# 输入处理n,target=map(int,input().split())nums=list(map(int,input().split()))ans=solve(nums,target)print(" ".join(map(str,ans)))

解题思路

1. 暴力枚举法：最直观的方法是使用双重循环，遍历数组中的每一对数，检查它们的和是否等于target。这种方法的时间复杂度为O ( n 2 ) O(n^2)O(n2)，在数据量较大时效率较低。
2. 哈希表法：为了提高效率，可以使用哈希表（字典）来存储数组中的元素及其对应的下标。遍历数组时，对于每个元素nums[i]，检查target - nums[i]
   是否在哈希表中。如果存在，则返回这两个数的下标；否则，将当前元素及其下标存入哈希表。这种方法的时间复杂度为O ( n ) O(n)O(n)，空间复杂度为
   O ( n ) O(n)O(n)。

• 时间复杂度：哈希表法的时间复杂度为O ( n ) O(n)O(n)，因为只需要遍历数组一次。
• 空间复杂度：哈希表法的空间复杂度为O ( n ) O(n)O(n)，因为需要存储数组中的元素及其下标。

2、字母异位词分组

题目描述

给你一个字符串数组strs，请你将字母异位词组合在一起。可以按任意顺序输出结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。

输入输出描述

输入：共两行，

• 第一行：一个整数n，代表字符串数组的长度；
• 第二行：n个字符串，表示字符串数组strs的元素，字符串之间以空格分隔。

输出：输出结果列表，每一行表示一组。每一组的字符串以空格分隔。

样例：
输入：
6
eat tea tan ate nat bat
输出：
bat
nat tan
ate eat tea

代码实现

fromcollectionsimportdefaultdictdefgroupAnagrams(strs):# 哈希表：key为排序后的字符串，value为对应的异位词列表hash_table=defaultdict(list)forsinstrs:# 对字符串排序，将排序后的结果作为键sorted_s=sorted(s)key="".join(sorted_s)# 将原字符串加入对应的异位词列表hash_table[key].append(s)# 返回所有异位词分组returnlist(hash_table.values())# 输入处理n=int(input())strs=input().split()ans=groupAnagrams(strs)forgroupinans:print(" ".join(group))

解题思路

核心思想：字母异位词的特点是，它们的字母组成相同，只是排列顺序不同。因此，可以通过对每个字符串进行排序，将排序后的字符串作为键，将原始字符串作为值存入哈希表中。最后，将哈希表中的值提取出来，即为分组后的结果。

1. 排序法：遍历字符串数组，对每个字符串进行排序，将排序后的字符串作为键，原始字符串作为值存入哈希表。最后，将哈希表中的值提取出来，即为分组后的结果。

• 时间复杂度：O ( n ⋅ k log ⁡ k ) O(n \cdot k \log k)O(n⋅klogk)，其中n是字符串数组的长度，k是字符串的最大长度。排序每个字符串的时间复杂度为O ( k log ⁡ k ) O(k \log k)O(klogk)，遍历字符串数组的时间复杂度为O ( n ) O(n)O(n)。
• 空间复杂度：O ( n ⋅ k ) O(n \cdot k)O(n⋅k)，哈希表存储所有字符串。

3、最长连续序列

题目描述

给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为O ( n ) O(n)O(n)的算法解决此问题。

输入输出描述

输入：共两行，

• 第一行：一个整数n，代表数组nums的长度；
• 第二行：n个整数，表示数组nums的元素，数字之间以空格分隔。

输出：一个整数，代表最长连续序列的长度。

样例：
输入：
6
100 4 200 1 3 2
输出：
4
说明：最长数字连续序列是[1, 2, 3, 4]，它的长度为 4。

代码实现

defsolve(nums):n=len(nums)# 构建哈希集合，用于 O(1) 时间复杂度查询nums_set=set(nums)ans=0fornuminnums:# 寻找序列的起点：如果 num-1 不在集合中，则 num 是起点ifnum-1notinnums_set:cur=1i=1# 依次检查 num+1, num+2, ... 是否存在whileTrue:ifnum+iinnums_set:cur+=1i+=1ans=max(ans,cur)else:breakreturnans# 输入处理n=int(input())nums=list(map(int,input().split()))ans=solve(nums)print(ans)

解题思路

本题的目标是找到数组中最长的连续整数序列，并且要求算法的时间复杂度为O(n)。可以使用哈希集合（HashSet）来实现高效查找，从而避免排序带来的 O(nlogn) 复杂度。方法：哈希表 + 贪心

• 1、构建哈希集合：由于查找某个元素是否存在的操作在哈希表中是 O(1) 复杂度，因此可以使用 set 存储数组中的所有数，方便后续查询。
• 2、遍历数组，寻找连续序列的起点：对于每个数字 num，如果 num - 1 不在哈希集合中，则 num 是一个序列的起点。以该 num为起点，不断检查 num + 1, num + 2, … 是否存在于集合中，计算序列的长度。
• 3、记录最大序列长度：通过遍历所有可能的起点，不断更新最长序列长度。
• 时间复杂度：构建哈希集合 O(n)，遍历数组 O(n)，查找连续序列 O(n)（每个元素最多只会被访问两次），总时间复杂度为 O(n)。
• 空间复杂度：O(n)，需要使用哈希集合存储数组中的所有元素。

双指针

1、移动零

题目描述

给定一个数组nums，将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请你注意，必须在不复制数组的情况下原地对数组进行操作。

输入输出描述

输入：共两行，

• 第一行：一个整数n，代表数组nums的长度；
• 第二行：n个整数，表示数组nums的元素，数字之间以空格分隔。

输出：一行n个整数，表示操作后的数组，数字之间以空格分隔。

样例1：
输入：
5
0 1 0 3 12
输出：
1 3 12 0 0

样例2：
输入：
1
0
输出：
0

代码实现

classSolution:defmoveZeroes(self,nums):n=len(nums)i=0# 记录非零元素应放置的位置# 遍历数组，将非零元素移到前面forjinrange(n):ifnums[j]!=0:nums[i],nums[j]=nums[j],nums[i]# 交换非零元素到前面i+=1# 移动非零元素位置索引# 读入数据并调用函数n=int(input().strip())nums=list(map(int,input().split()))Solution().moveZeroes(nums)print(" ".join(map(str,nums)))

解题思路

本题要求将数组中的 0 全部移动到末尾，且保持非零元素相对顺序，原地修改数组。
采用双指针法：一个指针记录当前非零元素应该存放的位置，另一个指针遍历数组。

1. 遍历数组，遇到非零元素就放到前面记录的位置，然后记录指针后移。
2. 遍历完成后，将记录指针之后的所有位置全部赋值为 0。
   时间复杂度：O ( n ) O(n)O(n)
   空间复杂度：O ( 1 ) O(1)O(1)

2、盛最多水的容器

题目描述

给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

输入输出描述

输入：共两行，

• 第一行：一个整数n，代表数组height的长度；
• 第二行：n个整数，表示数组height的元素，数字之间以空格分隔。

输出：一个整数，表示容器可以储存的最大水量。

样例：
输入：
9
1 8 6 2 5 4 8 3 7
输出：
49
样例图示

图中垂直线代表输入数组[1，8，6，2，5，4，8，3，7]。在此情况下·容器能够容纳水（表示为蓝色部分）的最大值为49。

代码实现

classSolution:defmaxArea(self,height):""" 双指针法求解最大容积 :param height: List[int] 代表垂线的高度数组 :return: int 最大水容量 """left,right=0,len(height)-1# 初始化左右指针max_area=0# 记录最大面积whileleft<right:# 计算当前区域的容量area=min(height[left],height[right])*(right-left)max_area=max(max_area,area)# 移动短板ifheight[left]<height[right]:left+=1else:right-=1returnmax_area# 读取输入if__name__=="__main__":n=int(input())# 读取整数 nheight=list(map(int,input().split()))# 读取数组solution=Solution()print(solution.maxArea(height))

解题思路

本题的目标是找到两条竖线，使得它们与x轴形成的容器能容纳最多的水。水的容量由较短的竖线高度和两条竖线的横坐标距离决定，即：
容积 = min(height[left], height[right]) × (right - left)
最直观的解法是暴力枚举两条竖线的所有可能组合，但时间复杂度为O ( n 2 ) O(n^2)O(n2)，会超时。
双指针优化：
由于水的容量受限于较短的竖线高度，我们可以使用双指针法来优化：

1. 初始化：左右指针分别放在数组的最左和最右。
2. 计算当前容积，记录最大值。
3. 移动指针：
   • 如果height[left] < height[right]，移动左指针left++（因为容量受短板影响，试图寻找更高的左边界）。
   • 否则，移动右指针right--（寻找更高的右边界）。
4. 重复直到left == right。
   这样，每个元素最多被访问一次，总时间复杂度为O ( n ) O(n)O(n)，是最优解法。

时间复杂度：O ( n ) O(n)O(n)，每个元素最多被访问一次。
空间复杂度：O ( 1 ) O(1)O(1)，只使用了常数级别的变量。

3、三数之和

题目描述

给定一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你输出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

输入输出描述

输入：共两行，

• 第一行：一个整数n，代表数组nums的长度；
• 第二行：n个整数，表示数组nums的元素，数字之间以空格分隔。

输出：输出所有满足条件的三元组，每行代表一个三元组，三元组的数字之间以空格分隔。

样例：
输入：
6
-1 0 1 2 -1 -4
输出：
-1 -1 2
-1 0 1

代码实现

classSolution:defthreeSum(self,nums):""" 三数之和，双指针法 :param nums: List[int] 代表输入数组 :return: List[List[int]] 符合条件的三元组列表 """nums.sort()# 先排序n=len(nums)res=[]foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:# 跳过重复元素continueleft,right=i+1,n-1# 左右指针whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal<0:left+=1eliftotal&