一、53. 最大子数组和
思路 1：前缀和优化
维护最小前缀和，避免双重循环。
class Solution:
def maxSubArray(self, nums):
if len(nums) == 1:
return nums[0]
res = float('-inf')
preSum = 0
minPreSum = 0
for n in nums:
preSum += n
res = max(res, preSum - minPreSum)
minPreSum = min(minPreSum, preSum)
return res
思路 2：动态规划
定义 dp[i] 表示以 nums[i] 结尾的最大子数组和。状态转移方程为 dp[i] = max(dp[i-1], 0) + nums[i]。
class Solution:
def maxSubArray(self, nums):
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1], 0) + nums[i]
return max(dp)
二、56. 合并区间
思路
先将 intervals 中的区间按起始位置排序。遍历区间，若当前区间与结果集最后一个区间有交集则合并，否则加入新区间。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda p: p[0])
res = []
for p in intervals:
if res and p[0] <= res[-1][1]:
res[-1][1] = max(res[-1][1], p[1])
else:
res.append(p)
return res
三、189. 轮转数组
思路
使用三次反转法实现原地旋转，避免额外空间开销。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
def reverse(i, j):
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)
四、238. 除自身以外数组的乘积
思路
前后缀分解。维护 pre[i] 表示 0 到 i-1 的乘积，suf[i] 表示 i+1 到 n-1 的乘积。
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
pre = [1] * n
for i in range(1, n):
pre[i] = pre[i-1] * nums[i-1]
suf = [1] * n
for i in range(n-2, -1, -1):
suf[i] = suf[i+1] * nums[i+1]
return [p * s for p, s in zip(pre, suf)]
五、41. 缺失的第一个正数
思路
将每个数字放到自己值对应的索引位置上（原地哈希）。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]:
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
