题目一：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。
关键数据结构：
列表 List[int]，本质上是一维数组
关键思路：
任意一个连续子数组，都是以nums中的某个元素num[i]结尾，用dp[i]表示以nums[i]元素结尾的数组。如果dp[i-1]>0，会让nums[i]变大；反之如果是负数只会让nums[i]变小，不如从nums[i]重新开始。
dp[i]可以通过递归思想来表示，即dp[i]=dp[i-1]+nums[i]（i>1）；dp[0]=nums[0](i=0)
代码:
class Solution: def maxSubArray(self, nums: List[int]) -> int: # curr_sum 表示以当前元素结尾的最大子数组和 # max_sum 表示全局最大子数组和 curr_sum = max_sum = nums[0] for num in nums[1:]: # 如果 curr_sum 是负数，那么它对 num 没有贡献，应该从 num 重新开始 # 如果 curr_sum 是正数，那么加上 num 可能更好 # 下面的 max(num, curr_sum + num) 就是做这个选择 curr_sum = max(num, curr_sum + num) # 更新全局最大值 max_sum = max(max_sum, curr_sum) return max_sum
题目二：
给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。
关键数据结构：
列表
关键思路：
将一个数组向右轮转k个位置，可以如此理解：
先将整个数组翻转，然后在位置k处将数组分割成两部分，再把两部分的数组翻转回去。
如[1,2,3,4,5,6]向右轮转2个位置，可以先把数组翻转：[6,5,4,3,2,1]
然后分割为[6,5][4,3,2,1]分别翻转，得到[5,6,1,2,3,4]，即所要求的结果
显然此种翻转是具有周期性的；当k>>n时，可以通过k%n获得等价翻转次数
代码中通过翻转函数来实现翻转操作，翻转函数本身使用了双指针定义。
代码：
class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k = k % n # 辅助反转函数 def reverse(start, end): while start < end: nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1 # 三次反转 reverse(0, n - 1) # 反转整个数组 reverse(0, k - 1) # 反转前k个 reverse(k, n - 1) # 反转剩余部分
题目三：
以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
关键数据结构：
List[List[int]]，即列表的列表
关键方法：
intervals.sort(key=lambda x: x[0]) 按照x元素中的第一个位置的大小排序
关键思路：
如果要合并重叠区间，最好的方法是首先把区间按左端点大小排列起来，使得可以合并的区间都是相邻的；判断两个区间是否重叠，实际上就是判断一个区间的终点是否大于另一个区间的起点。区间通过列表来表示，区间的集合则通过列表的列表来表示。
代码：
class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) # 按起点排序 merged = [] for interval in intervals: # 如果结果为空或不重叠，直接添加 if not merged or merged[-1][1] < interval[0]: #merged[-1]表示取merged中最后一个元素 merged.append(interval) else: # 重叠则合并，取最大右端点 merged[-1][1] = max(merged[-1][1], interval[1]) return merged
