基础算法精讲·题目汇总灵茶山艾府 - 【基础算法精讲】- GitHub视频灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频相向双指针01 两数之和 三数之和课程讲解167. 两数之和 II - 输入有序数组暴力O(n^2)的时间复杂度没有利用到数组已经排好序的性质双指针O(n)的时间复杂度暴力法是找两个数加起来和target比较花费O(1)的时间知道O(1)的信息。而优化后的做法是把当前剩下的最小的数和最大的数加起来和target比较比完之后就知道其中一个数和其他任何一个数相加都是小于target或大于target的花费O(1)的时间知道O(n)的信息class Solution: def twoSum(self, numbers: List[int], target: int) - List[int]: left, right 0, len(numbers)-1 while left right: if numbers[left] numbers[right] target: break elif numbers[left] numbers[right] target: right - 1 else: left 1 return [left 1, right 1]时间O(n)空间O(1)15. 三数之和经过上题的启发如果数组有序就可以使用相向双指针。故本题先对数组排序三元组的顺序并不重要那么可以 i j k答案中不可以包含重复的三元组那么只要当前枚举的这个数和上一个数是相同的就跳过nums[i] nums[j] nums[k] 0转变一下nums[j] nums[k] -nums[i]就跟上题一样了class Solution: def threeSum(self, nums: list[int]) - list[list[int]]: nums.sort() res [] n len(nums) for i in range(n-2): # 后面留n-1, n-2位置给j和k x nums[i] if i 0 and x nums[i-1]: # 去重 continue j, k i1, n-1 # 下面跟上题一样 while j k: s x nums[j] nums[k] if s 0: k - 1 elif s 0: j 1 else: res.append([x, nums[j], nums[k]]) j 1 while j k and nums[j] nums[j-1]: # 去重 j 1 k - 1 while k j and nums[k] nums[k1]: # 去重 k - 1 return res优化# 剪枝优化 if x nums[i1] nums[i2] 0: break if x nums[-1] nums[-2] 0: continue时间O(n^2)排序O(nlogn)for循环里嵌套while循环O(n^2)空间O(1)课后作业2824. 统计和小于目标的下标对数目16. 最接近的三数之和18. 四数之和611. 有效三角形的个数02 接雨水 前后缀分解课程讲解11. 盛最多水的容器容器的高度取决于短的这条线容器的宽度取决于这两条线的距离下标的差看图中短的那条红色的线如果中间的线比它短那么面积的宽度和高度都变小不会比蓝色的面积大如果中间的线比它长那么面积的宽度变小高度不变这里的高度是接水的高度取决于两个高度的最小值也不会比蓝色的面积大中间的任何一条线都无法跟它构成容量更大的容器换句话说如果要容纳更多的水比蓝色区域面积更大肯定不会包含短的那条红色的线所以可以直接去掉在剩下的线中继续找class Solution: def maxArea(self, height: List[int]) - int: res 0 left, right 0, len(height) - 1 while left right: # 此时还可以构成面积 area (right - left) * min(height[left], height[right]) res max(res, area) # 哪条线短就移动哪条 if height[left] height[right]: left 1 else: right - 1 return res时间O(n)空间O(1)42. 接雨水假设每个位置都有一个宽度为1的桶计算能接多少水就需要计算左边这块木板的高度取决于左边的max因为高于这个高度的水会从左边流出去和右边这块木板的高度取决于右边的max取两者的min前后缀分解需要额外两个数组第一个数组存储从最左边到第i个位置前缀的最大高度为前缀的最大值第二个数组存储从最右边到第i个位置后缀的最大高度为后缀的最大值对于每一个前缀最大值可以用上一个前缀最大值和当前高度比较取max从左到右算得到当前的前缀最大值对于每一个后缀最大值同上只是从右到左算最后同时遍历高度、前缀最大值 pre_max 和后缀最大值 suf_max累加min(前缀最大值, 后缀最大值) - 高度 表示每个水桶能接的水即为最后结果class Solution: def trap(self, height: List[int]) - int: n len(height) # 前缀最大值 pre_max [0] * n pre_max[0] height[0] for i in range(1, n): pre_max[i] max(pre_max[i-1], height[i]) # 比较上一个前缀最大值和当前高度取max # 后缀最大值 suf_max [0] * n suf_max[-1] height[-1] for i in range(n-2, -1, -1): suf_max[i] max(suf_max[i1], height[i]) # 计算答案 ans 0 for h, pre, suf in zip(height, pre_max, suf_max): ans min(pre, suf) - h return ans时空间复杂度都是O(n)相向双指针最优解法第一种做法在空间复杂度上还可以优化不需要创建额外数组如果前缀最大值比后缀最大值小那么左边这个木桶的容量就是前缀最大值算完之后把它向右扩展反之如果后缀最大值比前缀最大值小那么右边这个木桶的容量就是后缀最大值算完之后把它向左扩展用两个指针分别指向最左0和最右边len-1class Solution: def trap(self, height: List[int]) - int: n len(height) ans 0 left, right 0, n-1 pre_max, suf_max 0, 0 # 前缀最大值和后缀最大值 while left right: # 更新前缀最大值和后缀最大值 pre_max max(pre_max, height[left]) suf_max max(suf_max, height[right]) if pre_max suf_max: ans pre_max - height[left] left 1 else: ans suf_max - height[right] right - 1 return ans时间O(n)空间O(1)单调栈代码随想录思路详见 单调栈经典来袭LeetCode:42.接雨水单调递增栈求右边第一个比它大的元素单调栈里存放的是已经遍历过的元素中间柱子的下标栈顶元素栈里存的是下标左边第一个比它高的柱子的下标把上面栈顶元素弹出后的新栈顶元素右边~当前遍历元素的下标当前遍历元素 栈顶元素时左右取个min再减去中间柱子的高度为凹槽的高度之间的距离为凹槽的宽度由此累加面积class Solution: def trap(self, height: List[int]) - int: stack [0] # 栈里存放下标 rain 0 for i in range(1, len(height)): if height[i] height[stack[-1]]: # 符合单调递增栈的规则直接入栈 stack.append(i) elif height[i] height[stack[-1]]: # 先弹出再加入可以节省一步计算 stack.pop() stack.append(i) else: while stack ! [] and height[i] height[stack[-1]]: mid stack[-1] # 中间柱子的下标为当前栈顶元素 stack.pop() if stack ! []: left stack[-1] # 左边柱子的下标为当前栈顶元素弹出后的栈顶元素 right i # 右边柱子的下标为当前遍历元素 # 计算凹槽的高和宽 high min(height[left], height[right]) - height[mid] width right - left - 1 rain high * width stack.append(i) return rain课后作业125. 验证回文串2105. 给植物浇水 II滑动窗口同向双指针【题单】滑动窗口https://leetcode.cn/circle/discuss/0viNMK/03 最短 最长 方案数课程讲解在子数组、子串问题中经常会用到双指针这一技巧。只有满足了单调性才能使用双指针209. 长度最小的子数组class Solution: def minSubArrayLen(self, target: int, nums: List[int]) - int: n len(nums) ans n1 # 初始化为一个很大的数本题答案至多是n或inf s 0 left 0 # 枚举右端点 for right, x in enumerate(nums): # right: [0, n-1]; x nums[right] s x while s - nums[left] target: # 缩小窗口右移左端点 s - nums[left] left 1 if s target: ans min(ans, right-left1) return ans if ans n else 0 # 这里还有另一种写法 class Solution: def minSubArrayLen(self, target: int, nums: List[int]) - int: n len(nums) ans n1 # 或inf s 0 left 0 for right, x in enumerate(nums): # right: [0, n-1]; x nums[right] s x while s target: ans min(ans, right-left1) s - nums[left] left 1 return ans if ans n else 0时间O(n)空间O(1)注意不要以为for里套着while就是O(n^2)的时间复杂度因为left和right都是至多移动到n的713. 乘积小于 K 的子数组while条件还可以从不满足要求变成满足要求class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) - int: if k 1: return 0 ans 0 prod 1 left 0 for right, x in enumerate(nums): prod * x while prod k: prod prod / nums[left] left 1 # [l, r] 的乘积 k # 那么 [l, r] [l1, r] ... [r, r] 的乘积一定 k # 符合的子数组数目其实就是 r-l1 ans right-left1 return ans3. 无重复字符的最长子串由于每次都是接到一个没有重复元素的子串后面所以这个重复的元素一定来自接入的这个字符怎么判断是否有重复字符呢可以用一个哈希表记录字符的出现次数cnt Counter()会创建一个空的计数器对象类似于空字典{}但专门用于计数from collections import Counter class Solution: def lengthOfLongestSubstring(self, s: str) - int: ans 0 # 求的是最大值因此初始化为0 cnt Counter() # hashmap记录每个字符的出现次数 left 0 # 枚举右端点 for right, c in enumerate(s): cnt[c] 1 # 字符c出现次数1 while cnt[c] 1: # 将左端点右移 cnt[s[left]] - 1 left 1 ans max(ans, right-left1) # 字符个数 return ans时间O(n)空间O(128)或O(1)因为s由英文字母、数字、符号和空格组成可以当做是一个ASCII字符最多有128个。也可以理解成s里有多少个不同的字符O(len(set(s)))课后作业3090. 每个字符最多出现两次的最长子字符串2958. 最多 K 个重复元素的最长子数组2730. 找到最长的半重复子字符串1004. 最大连续 1 的个数 III2962. 统计最大元素出现至少 K 次的子数组2302. 统计得分小于 K 的子数组数目1658. 将 x 减到 0 的最小操作数3795. 不同元素和至少为 K 的最短子数组长度76. 最小覆盖子串