🚀 Week2 Day1 LeetCode 数组
最大子数组和
🧠 题目描述
给你一个整数数组 nums，请找出其中具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
💡 解法思路：前缀和 + 贪心
-
维护一个前缀和
pre_sum与历史最小前缀和min_pre_sum； -
每次更新最大子数组和
ans = max(ans, pre_sum - min_pre_sum)； -
当
pre_sum过大时更新最小前缀和以减小后续差值。
✅ 代码实现
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = -inf
min_pre_sum = pre_sum = 0
for x in nums:
pre_sum += x
ans = max(ans, pre_sum - min_pre_sum)
min_pre_sum = min(min_pre_sum, pre_sum)
return ans
🧩 复杂度分析
-
时间复杂度：O(n)
-
空间复杂度：O(1)
合并区间
🧠 题目描述
给定若干区间数组 intervals[i] = [start_i, end_i]，请合并所有重叠区间，并返回一个不重叠的区间数组。
示例
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 合并为 [1,6].
💡 解法思路：排序 + 合并扫描
-
先按照左端点升序排序；
-
若当前区间与前一区间重叠，则合并更新右端点；
-
否则直接加入结果集。
✅ 代码实现
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda p: p[0])
ans = []
for p in intervals:
if ans and p[0] <= ans[-1][1]:
ans[-1][-1] = max(ans[-1][1], p[1])
else:
ans.append(p)
return ans
🧩 复杂度分析
-
时间复杂度：O(n log n) （排序所需）
-
空间复杂度：O(n)
轮转数组
🧠 题目描述
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例
输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]
💡 解法思路：三次反转法
-
反转整个数组；
-
反转前
k个元素； -
反转剩余的
n-k个元素。
该方法利用原地反转完成旋转，无需额外空间。
✅ 代码实现
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
def reverse(i: int, j: int) -> None:
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
n = len(nums)
k %= n
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
🧩 复杂度分析
-
时间复杂度：O(n)
-
空间复杂度：O(1)
📘 小结
🔁 三题皆为数组高频题，熟练掌握能极大提升处理区间与数组类题的思维敏捷度。