最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
首次提交
想法
贪心：在遍历数组时，累加当前元素。如果当前累加和变成负数，则丢弃累加的结果，从下一个元素重新开始累加。在每一步都记录当前的最大和。
实现流程
- 初始化：
- 使用一个变量
max_sum保存全局最大和，初始化为数组的第一个元素。 - 使用另一个变量
current_sum保存当前子数组的累加和，初始化为 0。
- 使用一个变量
- 遍历数组：
- 将当前元素加入
current_sum。 - 如果
current_sum大于max_sum，更新max_sum。 - 如果
current_sum小于 0，重新将current_sum置为 0（因为负数对后续的累加没有贡献）。
- 将当前元素加入
- 返回
max_sum。
代码：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = nums[0] # 全局最大和
current_sum = 0 # 当前子数组的累加和
for num in nums:
current_sum += num
max_sum = max(max_sum, current_sum)
if current_sum < 0:
current_sum = 0
return max_sum
时间复杂度：
$O(n)$，只需遍历数组一次。
空间复杂度：
$O(1)$，只使用了常数级额外空间。
合并区间
以数组 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] 可被视为重叠区间。首次尝试
想法
使用双指针 left 和 right，其中 left 用于遍历，right 用于找到和当前区间 intervals[left] 重叠的区间。如果发现两个区间有重叠（即 temp[1] >= intervals[right][0]），则将 temp 更新为合并后的区间，并继续移动 right。将合并结果存入 result 中。
问题代码
class Solution:
def merge(self, intervals):
result = []
right = 1
for left in range(len(intervals)-1):
if left < right - 1:
continue
temp = [intervals[left][0], intervals[left][1]]
while temp[1] >= intervals[right][0]:
temp = [temp[0], intervals[right][1]]
right += 1
right += 1
result.append(temp)
return result
intervals = [[1,3],[2,6],[8,10],[15,18]]
# intervals = [[1,4],[4,5]]
solution = Solution()
print(solution.merge(intervals))问题
未排序问题： intervals 在逻辑处理前未进行排序。若输入区间未按 start 排序，程序无法正确处理。
数组越界： 在 while temp[1] >= intervals[right][0] 中，right 的索引可能越界，导致运行时错误。
逻辑不清晰：
if left < right - 1: continue这部分可能会跳过left索引的逻辑处理，导致某些区间被遗漏。right增加两次（while和后续的right += 1），这可能导致索引错乱。
复杂度
当前代码的复杂度接近 $O(n^2)$，因为每个区间可能通过 while 遍历多次，这会在处理较多区间时效率较低。
改进
- 排序： 先按区间的起点
start对intervals进行排序，以保证合并逻辑的正确性。 - 双指针逻辑： 通过一个单指针遍历
intervals，判断当前区间是否与上一个合并区间重叠。
代码
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# 边界处理：如果输入列表为空或仅有一个区间
if not intervals:
return []
# 通过lambda表达式对sorted按起点排序
sorted_intervals = sorted(intervals, key = lambda x:x[0])
result = []
min_num = sorted_intervals[0][0]
max_num = sorted_intervals[0][1]
for i in range(1,len(intervals)):
# 有重叠
if max_num >= sorted_intervals[i][0]:
if max_num < sorted_intervals[i][1]:
max_num = sorted_intervals[i][1]
else:
result.append([min_num, max_num])
min_num = sorted_intervals[i][0]
max_num = sorted_intervals[i][1]
result.append([min_num, max_num])
return result合并逻辑
- 如果当前区间的起点
sorted_intervals[i][0]小于或等于前一个区间的终点max_num，则尝试更新max_num。 - 如果没有重叠，将前一个区间加入结果，并更新
min_num和max_num。 - 最后，将最后一个区间添加到结果中，确保不遗漏。
注意事项
- lambda表达式排序
- 当有重叠区域时，仍要判断max_num是否大于
sorted_intervals[i][1], (例如[[1,5],[2,4]]) - 注意最后一个索引时，假如有重叠则只更新了max_num没有加入result列表，假如没有重叠则将之前的
[min_num, max_num]加入result列表，没有加入之后更新的[min_num, max_num]，因此需要在循环结束后再添加一个append().
时间复杂度
- 排序部分： $O(n \log n)$
- 遍历部分： $O(n)$
- 总复杂度： $O(n \log n)$
最终优化
代码
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
# 按起点排序
sorted_intervals = sorted(intervals, key=lambda x: x[0])
result = []
current_start, current_end = sorted_intervals[0]
for i in range(1, len(sorted_intervals)):
start, end = sorted_intervals[i]
if start <= current_end: # 有重叠
current_end = max(current_end, end)
else: # 无重叠，保存当前区间
result.append([current_start, current_end])
current_start, current_end = start, end
# 添加最后一个区间
result.append([current_start, current_end])
return result