LeetCode 热题 100 Python3易懂题解（更新中）

链接可直接跳转

哈希

1. 两数之和（简单）

给定一个整数数组 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], target = 6 输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6 输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

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]

这是最简单的做法，即直接遍历整个列表，从第一个值开始遍历，如果从当前位置到最后位置中有和当前位置值相加为目标值的即返回这两个位置。

49. 字母异位词分组（中等）

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

• 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
• 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
• 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: d=defaultdict(list) for s in strs:.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()将其转换为列表并返回，就得到了最终答案 。

128. 最长连续序列（中等）

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9

示例 3：

输入：nums = [1,0,1,2] 输出：3

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

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。

双指针

283. 移动零（简单）

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]输出:[1,3,12,0,0]

示例 2:

输入: nums = [0]输出:[0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ 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 

这一题很巧妙的点在于用双指针可以互换数组里面数字的位置，可以自己画一下图理解一下。

11. 盛最多水的容器（中等）

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

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

示例 2：

输入：height = [1,1] 输出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

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循环，但是时间复杂度过不去，所以用双指针。

首先在数组首尾设立双指针，这个时候最大面积等于指针指向位置中较小的数乘以指针之间的距离。

这个代码的重点就是指针的移动：

        首先置为首尾，这时候只能移动值较小的指针。

        可以模拟一下，如果移动较大值的指针，那么指针间的距离减小了，指针指向位置中较小的数只可能不变或者减小，这样面积一定减小。

        反之，我们移动较小值的指针，面积则可能增大。

最后返回最大面积即可。

15. 三数之和 （中等）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：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] 。 注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

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往左移的同时跳过重复值；

最后返回数组。

42. 接雨水 (困难）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5] 输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

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指针左移。

最后返回res。

还看到一个很有意思的解法，按行遍历当前行能装多少容量的水：

也就是从第一行开始遍历，当前行为i，从左到右开始遍历墙的高度，如果高度大于等于i，说明右边有装下水的能力，开始更新以当前墙作为左墙的当前容量，从此往后，如果高度小于i，当前容量+1，如果大于等于i，把当前容量加入到总容量里去，当前容量置0，一直重复。

其实也就是说当前小于i并且俩边有高度大于i的墙则容量+1。（看文字有点难理解，自己拿数组推一下很简单）

滑动窗口

3. 无重复字符的最长子串（中等）🌟

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

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也就是不重复字符串长度的最大值。

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

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

示例 1:

输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 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记录子串的起始索引。

如果n>m直接返回空res数组。

然后创建初始值为0的俩个长度为26的数组，用来表示26个字母出现次数。

一个数组用来统计p中字母出现的次数，另一个统计滑动窗口里字母出现次数。数组相等就输出滑动窗口左端位置。

子串

560. 和为 K 的子数组（中等）

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2 输出：2

示例 2：

输入：nums = [1,2,3], k = 3 输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

下面是通不过时间复杂度的暴力解法：

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是记录当前前缀和数值出现的次数。

将presums[0]置为1，也就是前缀和为0目前出现过一次。当前前缀和为0。

遍历该数组，计算当前位置的前缀和。连续子数组的和为k的个数用res表示，此时res等于之前的res加上哈希表中当前前缀和减去k的位置的值，意思就是，比如presum-k这个前缀和如果出现了4次，那么presum-（presum-k）=k这个值就出现了四次，res+4。

然后把前缀和出现次数的哈希表中当前前缀和位置的值加一。

最后返回res。