哈希1. 两数之和 - 力扣LeetCodeclass Solution: def twoSum(self, nums: List[int], target: int) - List[int]: d {} for i in range(len(nums)): if nums[i] in d: return [i,d[nums[i]]] d[target-nums[i]] i return None49. 字母异位词分组 - 力扣LeetCode排序or计数class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: d collections.defaultdict(list) for s in strs: mp .join(sorted(s)) d[mp].append(s) return list(d.values())时间复杂度o(nklog(k))空间复杂度o(nk)class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: d collections.defaultdict(list) for s in strs: counts [0]*26 for c in s: counts[ord(c)-ord(a)] 1 # list不能作为key d[tuple(counts)].append(s) return list(d.values())时间复杂度o(nk)空间复杂度o(nk)128. 最长连续序列 - 力扣LeetCodeclass Solution: def longestConsecutive(self, nums: List[int]) - int: # 如果出现重复元素那么就需要我们不断的去重复判断但是对于结果没有任何影响所以需要先去重 # 如果去重以后元素能按照顺序排列那么接下来就是判断起点和最大长度的过程 nums_set sorted(set(nums)) n len(nums_set) if n2: return n res cur 1 for i in range(1,n): # if nums_set[i]-1!nums_set[i-1]: # res max(res,cur) # 这样写的bug是如果全部连续那么没有办法触发条件 # cur 1 # else: # cur 1 if nums_set[i]-1nums_set[i-1]: cur 1 res max(res,cur) else: cur 1 return res时间复杂度o(nlogn)空间复杂度o(n)class Solution: def longestConsecutive(self, nums: List[int]) - int: # 如果出现重复元素那么就需要我们不断的去重复判断但是对于结果没有任何影响所以需要先去重 # 其实没必要排序我们只要找到连续序列的起点开始计数即可 nums_set set(nums) n len(nums_set) if n2: return n res 1 for num in nums_set: if num-1 not in nums_set: cur 1 while num1 in nums_set: cur 1 num 1 res max(res,cur) return res时间复杂度o(n) # 尽管for嵌套了while但是由于if起点的判断每一个元素在整体仅仅被遍历一次空间复杂度o(n)双指针283. 移动零 - 力扣LeetCodeclass Solution: def moveZeroes(self, nums: List[int]) - None: Do not return anything, modify nums in-place instead. # 快慢指针 # 慢指针指向非0元素的下一个元素 slow fast 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow],nums[fast] nums[fast],nums[slow] slow 1时间复杂度o(n)空间复杂度o(1)11. 盛最多水的容器 - 力扣LeetCodeclass Solution: def maxArea(self, height: List[int]) - int: # 左右指针对于每个柱子它能接的最多的雨水就是距离它最远的柱子宽度乘以矮柱子的高度 # 所以矮柱子的移动是有可能带来整体的更多的雨水的 left,right 0,len(height)-1 res 0 while leftright: res max(res,(right-left)*min(height[left],height[right])) if height[left]height[right]: left 1 else: right - 1 return res时间复杂度o(n)空间复杂度o(1)15. 三数之和 - 力扣LeetCodeclass Solution: def threeSum(self, nums: list[int]) - list[list[int]]: res [] # 注意题目要求不重复所以必须排序排序可以方便去重 nums_sort sorted(nums) n len(nums_sort) for f in range(n-2): if f!0 and nums_sort[f]nums_sort[f-1]: continue # 三数之和等于0那么first应该小于等于0 if nums_sort[f]0: break s,t f1,n-1 while st: cur nums_sort[f]nums_sort[s]nums_sort[t] if cur 0: res.append([nums_sort[f],nums_sort[s],nums_sort[t]]) # 去重 while st and nums_sort[s1]nums_sort[s]: s 1 while st and nums_sort[t-1]nums_sort[t]: t - 1 # 去重后进位 s 1 t - 1 elif cur 0: t - 1 else: s 1 return res时间复杂度o(n*n) # 最差就是内外都是遍历一遍空间复杂度o(logn) # 排序带来的结果的存储不计入42. 接雨水 - 力扣LeetCodeclass Solution: def trap(self, height: List[int]) - int: # 接雨水就用单调栈求解是最好的 # 柱子接多少雨水完全取决于右侧柱子 # 一旦右侧柱子比当前高那么当前柱子就能接雨水接多少取决于左臂和右侧柱子 n len(height) if n2: return 0 stack [] res 0 for i in range(n): # 当前柱子高stack[-1]就是坑底,stack[-2]才是左臂 # 按照现在的弹出顺序整个栈一定是栈顶小的stack[-1]stack[-2] while stack and height[i]height[stack[-1]]: bottom stack.pop() if not stack: break left stack[-1] # 左臂并不弹出 res (i-left-1)*(min(height[left],height[i])-height[bottom]) stack.append(i) return res时间复杂度O(n) # for里面嵌套while但是while仅仅是作用于stack每个元素入栈出栈一次最多空间复杂度O(n)滑动窗口3. 无重复字符的最长子串 - 力扣LeetCodeclass Solution: def lengthOfLongestSubstring(self, s: str) - int: # 快慢指针确定窗口集合确定不重复但是注意集合也是需要动态的出现重复删除的是左侧 # 23245到了2重复了但是删的是左侧的2而不是放弃全部窗口 # 223245用while而不是if res 0 d set() left 0 for right in range(len(s)): while s[right] in d: d.remove(s[left]) left 1 d.add(s[right]) res max(res,len(d)) return res时间复杂度O(n) # for里面嵌套while但是d也最多存一遍所有的字符空间复杂度O(n)438. 找到字符串中所有字母异位词 - 力扣LeetCodeclass Solution: def findAnagrams(self, s: str, p: str) - List[int]: # 异位词的判断需要靠字典确定字符和数量 # 借助collections.Counter()库可以解决 # 但是我们不能对每一个字符串都这样去判断 # 仅仅判断第一个对应串其他是一个增删的逻辑 m,n len(s),len(p) res [] if mn: return res ds collections.Counter(s[:n]) dp collections.Counter(p) if ds dp: res.append(0) # 构造窗口判断 slow 0 for fast in range(n,m): ds[s[fast]] 1 ds[s[slow]] - 1 # 下面的判断没有任何作用仅仅是减少存储不加完全可以 if ds[s[slow]] 0: del ds[s[slow]] slow 1 if ds dp: res.append(slow) return res时间复杂度O(n)空间复杂度O(n)子串560. 和为 K 的子数组 - 力扣LeetCodeclass Solution: def subarraySum(self, nums: List[int], k: int) - int: # 求的是子数组所以排序不可用 # 数字有正有负所以快慢指针也会失效 # 求解思路是前缀和如果i-j的子数组求和为k说明j的前缀和减去i的前缀和为k res 0 pre 0 d {0:1} # 比如恰好每个元素都是k for n in nums: pre n if pre-k in d: res d[pre-k] # 可能不止一个 d[pre] d.get(pre,0)1 return res时间复杂度O(n)空间复杂度O(n)239. 滑动窗口最大值 - 力扣LeetCodeclass Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: # 在滑动窗口中只要出现了最大值那么滑动窗口里面就是确定的 # 但是如果原定的最大值离开了滑动窗口则需要新的最大值 # 而这个过程满足的是先进先出 # 所以考虑一个维护顺序的队列 # 队列的队首是最大的元素从队首到队尾元素依次变小 # 队列里面存idx需要判断长度是否达到滑动窗口 dq [] res [] for i in range(k): # 不是所有的元素都存而是说大元素之前的小元素没必要存 # 但是大元素之后的小元素是需要存的 # 所以从队尾开始往前走只要大就弹出前面的 # 但是从队尾开始如果小那就得存起来 while dq and nums[dq[-1]]nums[i]: dq.pop() dq.append(i) res.append(nums[dq[0]]) for i in range(k,len(nums)): while dq and nums[dq[-1]]nums[i]: dq.pop() dq.append(i) if i-dq[0]k: dq.pop(0) res.append(nums[dq[0]]) return res时间复杂度O(n) # for里面嵌套while但是d也最多存一遍所有的字符空间复杂度O(k)76. 最小覆盖子串 - 力扣LeetCodeclass Solution: def minWindow(self, s: str, t: str) - str: # 其实还是异位词的思路但是是子数组所以对前后有点限制 m,n len(s),len(t) if mn: return ds collections.Counter() dt collections.Counter(t) min_len m1 min_left left 0 cur 0 # 记录一下有多少个字符满足了 required len(dt) # 需要满足这些 for right in range(m): ds[s[right]] 1 # 看看是否可以满足一个 if s[right] in dt and ds[s[right]]dt[s[right]]: cur 1 # 假如我们现在已经全部满足了那就尝试缩小左边界看看能不能更小 # 注意满足条件是cur required # 一次一步边收缩边更新状态 while cur required: if right-left1 min_len: min_left left min_len right - left 1 # 然后把left移出窗口其实就是1但是在这之前要判断是否破坏了成立性 if s[left] in dt: ds[s[left]] - 1 if ds[s[left]] dt[s[left]]: cur - 1 left 1 return if min_len m1 else s[min_left:min_leftmin_len]时间复杂度O(nm) # for里面嵌套while但是实际一个移动right一个移动left各自其实均只有一遍再加上构造counter的n。空间复杂度O(|Σ|)其中 Σ 是字符集。普通数组53. 最大子数组和 - 力扣LeetCodeclass Solution: def maxSubArray(self, nums: List[int]) - int: # 很明显的动态规划 # 对于每一个点要么从这里开始要么作为上一个子数组的一部分 n len(nums) dp [0]*n dp[0] nums[0] for i in range(1,n): dp[i] max(dp[i-1]nums[i],nums[i]) return max(dp) # 注意最后一个不一定是最大的时间复杂度O(n)空间复杂度O(n)56. 合并区间 - 力扣LeetCodeclass Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: # 首元素排序然后逐个添加即可 intervals_sort sorted(intervals,key lambda x:x[0]) res [intervals_sort[0]] for i in range(1,len(intervals_sort)): if intervals_sort[i][0] res[-1][1]: res[-1][1] max(res[-1][1],intervals_sort[i][1]) else: res.append(intervals_sort[i]) return res时间复杂度O(nlogn) # 合并只有n但是排序有nlogn空间复杂度O(logn) # res没有额外空间但是排序需要logn189. 轮转数组 - 力扣LeetCodeclass Solution: def rotate(self, nums: list[int], k: int) - None: Do not return anything, modify nums in-place instead. k k % len(nums) # k可能很大 nums[:] nums[len(nums)-k:]nums[:len(nums)-k]时间复杂度O(n)空间复杂度O(n) # 等价于其他的数组作为中间变量238. 除了自身以外数组的乘积 - 力扣LeetCodeclass Solution: def productExceptSelf(self, nums: List[int]) - List[int]: # 要想不重复遍历就一定需要借助前缀的思想 # 但是我们是除了自身的前后的元素 # 所以思考一下就想到应该是前缀后缀都需要考虑 # 正向便利记录前缀后向遍历记录后缀 res [1] # 乘法的开始是1 n len(nums) for i in range(1,n): res.append(res[-1]*nums[i-1]) r 1 for i in range(n-2,-1,-1): r * nums[i1] res[i] * r return res时间复杂度O(n)空间复杂度O(1)41. 缺失的第一个正数 - 力扣LeetCodeclass Solution: def firstMissingPositive(self, nums: List[int]) - int: # 这个题目的本质其实是利用数组实现哈希 # 如果每一个正数恰好就在对应的数组位置上排列那么我们一遍历就知道哪一个最小正数不在 # 关键在于如何为每一个正数找到对应的位置 n len(nums) for i in range(n): # nums[nums[i]-1]!nums[i]看的是我应该在的那个房子里面是否住着我的值 # 如果换成nums[i]-1!nums[i]就不对了因为这会强制要求我应该在的房子里面必须住我自己 # [1,1]就会进入一个死循环在位置1,理论住的是2但是就会死循环交换 # 但是如果不用while呢 # 不用while肯定是不行的因为我的换只能保证目前对了换进来的新的nums[i]对房子的要求就变了 # [2,3,1] - [3,2,1]()第一次替换以后2对了但是3还是不对啊我们不能跳过位置0 - [1,2,3] # [3, 4, 2, 1] 如果是if那么将会很难归位 while 0nums[i]n and nums[nums[i]-1]!nums[i]: nums[nums[i]-1],nums[i]nums[i],nums[nums[i]-1] # while 不会带来更多时间复杂度每个位置至多一次就找到正确的位置了 for i in range(n): if nums[i]!i1: return i1 return n1时间复杂度O(n) # while 不会带来更多时间复杂度每个位置至多一次就找到正确的位置了空间复杂度O(1)矩阵73. 矩阵置零 - 力扣LeetCodeclass Solution: def setZeroes(self, matrix: List[List[int]]) - None: Do not return anything, modify matrix in-place instead. # 思路很简单设置一个标记矩阵 # 但是更简单的思路是直接设置一个行列向量就可以完成标记 m,n len(matrix),len(matrix[0]) row,col [0]*m,[0]*n for i in range(m): for j in range(n): if matrix[i][j] 0: row[i] col[j] 1 for i in range(m): for j in range(n): if row[i] or col[j]: matrix[i][j] 0时间复杂度O(nm)空间复杂度O(nm)