53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
示例 1：
**输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
类似于动态规划方法，dp[i]表示以i结尾的元素的最大子数组和。状态转移方程：
dp[i]=max(dp[i-1] + nums[i], nums[i])
dp[0]=nums[0]
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
result = nums[0]
for i in range(1, size):
dp[i] = max(dp[i-1]+nums[i], nums[i])
result = max(result, dp[i])
return result
dp[i]的计算和dp[i-1], nums[i]有关，也可以把dp数组去掉，使用pre、cur来代替，pre=dp[i-1], cur=dp[i]，节省空间。
56. 合并区间
以数组 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].
先对原数组intervals按照每个pair的第一个元素按照升序排序，遍历排序后的数组，同时将一个元素加到结果数组res中；当遍历到非第一个元素时，比较res数组的最后一个区间的右边界和当前区间的左边界，如果重合，即res[-1][1] < intervals[i][0], 进行区间合并，将res中最后一个区间的右边界更新为当前元素的右边界；如果不重合，直接加入到结果数组中。
区间合并：比如说intervals = [[1,4], [2,3]], 完全包围
res[-1][1] = max(intervals[i][1], res[-1][1])
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals = sorted(intervals, key=lambda x: x[0])
res = [intervals[0]]
for i in range(1, len(intervals)):
if intervals[i][0] <= res[-1][1]:
res[-1][1] = max(intervals[i][1], res[-1][1])
else:
res.append(intervals[i])
return res
对于append来说，可以把intervals[0]的操作和非重合操作合并起来，合并后的代码：
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda x : x[0])
merged = []
for i in intervals:
# 数组为空 or 区间不重合
if not merged or merged[-1][1] < i[0]:
merged.append(i)
else:
merged[-1][1] = max(i[1], merged[-1][1])
return merged
189. 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
利用python的数组切片，切片后的数组直接拼接得到最终结果。
num[:] = aaa, 实现数组的原地修改，而不是直接赋值—导致nums的地址改变。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
想办法通过数学运算推导出每个元素的最终位置，通过建立一个映射关系，遍历一次数组直接得到最终答案。
首先，要考虑k和N的关系，k有可能大于N，这个时候要对k = k % N，去除非必要操作。
(i + k) % N
arr_nums[(i + k) % N] = nums[i]
使用一个辅助数组，最后将辅助数组的顺序赋值给nums，实现原地修改。
另一种方法，通过多次翻转实现。
- reverse(nums) 7 6 5 4 3 2 1
- reverse(nums[:k %N]) 5 6 7 4 3 2 1
- reverse(nums[k %N:]) 5 6 7 1 2 3 4
238. 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，且在 O(_n_) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
不能使用除法，如果可以使用除法，我们可以计算一个乘积，同时结合当前元素是否为0特判。另一种思路，双层循环，result[i] = ply[0:i] * ply[i+1: ], 即按照本身定义计算，但是时间复杂度比较高。为了进行优化，可以使用另外的数组，存储lply[i] , rply[i+1:].
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n=len(nums)
L,R,ans=[0]*n,[0]*n,[0]*n
L[0]=1
for i in range(1,n):
L[i]=L[i-1]*nums[i-1] #i左边的乘积
R[n-1]=1
for i in reversed(range(n-1)):
R[i]=R[i+1]*nums[i+1] #i右边的乘积
for i in range(n):
ans[i]=L[i]*R[i]
return ans
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
for i in range(1, len(nums)):
res[i] = res[i - 1] * nums[i - 1]
suf = 1
for i in range(len(nums) - 1, -1, -1):
res[i] *= suf
suf *= nums[i]
return res
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
**输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
一种思路，for循环，遍历 1~N+1，判断是否在数组中，如果不再返回即可。另一种思路，置换法，理解为将数组排序后，理论上 i 下 值为 i+1，即nums[i]应该出现在下标i+1上，最后依次遍历找到第一个不符合关系的元素。
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[i], nums[nums[i] - 1] = 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
