3. 无重复字符的最长子串 - 力扣（LeetCode）
给定一个字符串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 <= 105s由英文字母、数字、符号和空格组成
from collections import defaultdict class Solution: def lengthOfLongestSubstring(self, s): lookup = defaultdict(int) start = 0 end = 0 max_len = 0 counter = 0 while end < len(s): if lookup[s[end]] > 0: counter += 1 lookup[s[end]] += 1 end += 1 while counter > 0: if lookup[s[start]] > 1: counter -= 1 lookup[s[start]] -= 1 start += 1 max_len = max(max_len, end - start) return max_len59. 螺旋矩阵 II - 力扣（LeetCode）
给你一个正整数n，生成一个包含1到n2所有元素，且元素按顺时针顺序螺旋排列的n x n正方形矩阵matrix。
示例 1：
输入：n = 3输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1输出：[[1]]
303. 区域和检索 - 数组不可变 - 力扣（LeetCode）
给定一个整数数组nums，处理以下类型的多个查询:
- 计算索引
left和right（包含left和right）之间的nums元素的和，其中left <= right
实现NumArray类：
NumArray(int[] nums)使用数组nums初始化对象int sumRange(int left, int right)返回数组nums中索引left和right之间的元素的总和，包含left和right两点（也就是nums[left] + nums[left + 1] + ... + nums[right])
示例 1：
输入：["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]输出：[null, 1, -1, -3]解释：NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
解法
按照原始题目，解法如下
class NumArray: def __init__(self, nums: list[int]): self.nums = nums def sumRange(self, left: int, right: int) -> int: pre_sum=[0]*(len(self.nums)+1) for i in range(len(self.nums)): pre_sum[i+1]=pre_sum[i] + self.nums[i] return pre_sum[right+1]-pre_sum[left]但是这种解法时间时间复杂度是O（n），因为每次调用sumRange都会执行一遍for循环。
如果输入的数组确定的话，频繁调用sumRange函数，就可以把前缀和的数组操作放在__init__函数中，这样时间复杂度可以认为接近O(1)
class NumArray: def __init__(self, nums: list[int]): pre_sum=[0]*(len(nums)+1) for i in range(len(nums)): pre_sum[i+1]=pre_sum[i] + nums[i] self.pre_sum = pre_sum def sumRange(self, left: int, right: int) -> int: return self.pre_sum[right+1]- self.pre_sum[left]560. 和为 K 的子数组 - 力扣（LeetCode）
给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的子数组的个数。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2输出：2
示例 2：
输入：nums = [1,2,3], k = 3输出：2
1109. 航班预订统计 - 力扣（LeetCode）
这里有n个航班，它们分别从1到n进行编号。
有一份航班预订表bookings，表中第i条预订记录bookings[i] = [firsti, lasti, seatsi]意味着在从firsti到lasti（包含firsti和lasti）的每个航班上预订了seatsi个座位。
请你返回一个长度为n的数组answer，里面的元素是每个航班预定的座位总数。
示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5输出：[10,55,45,25,25]解释：航班编号 1 2 3 4 5 预订记录 1 ： 10 10 预订记录 2 ： 20 20 预订记录 3 ： 25 25 25 25 总座位数： 10 55 45 25 25 因此，answer = [10,55,45,25,25]
示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2输出：[10,25]解释：航班编号 1 2 预订记录 1 ： 10 10 预订记录 2 ： 15 总座位数： 10 25 因此，answer = [10,25]
56. 合并区间 - 力扣（LeetCode）
以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3：
输入：intervals = [[4,7],[1,4]]输出：[[1,7]]解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
41. 缺失的第一个正数 - 力扣（LeetCode）
给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]输出：3解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]输出：2解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]输出：1解释：最小的正数 1 没有出现。
206. 反转链表 - 力扣（LeetCode）
给你单链表的头节点head，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]输出：[2,1]
示例 3：
输入：head = []输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
21. 合并两个有序链表 - 力扣（LeetCode）
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []输出：[]
示例 3：
输入：l1 = [], l2 = [0]输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按非递减顺序排列
141. 环形链表 - 力扣（LeetCode）
给你一个链表的头节点head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回true。 否则，返回false。
示例 1：
输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0输出：true解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1输出：false解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个有效索引。
进阶：你能用O(1)（即，常量）内存解决此问题吗？
142. 环形链表 II - 力扣（LeetCode）
给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用O(1)空间解决此题？
