目录
5.普通数组
5.1最大子数组和（中等）
5.2合并区间（中等）
5.3 轮转数组（中等）
5.4 除自身以外数组的乘积（中等）
5.5缺失的第一个正数（困难）
5.普通数组
5.1最大子数组和（中等）
题目描述：leetcode链接 53. 最大子数组和
给你一个整数数组
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
思路：
本题是经典的动态规划问题，动态规划问题有相似的解题方法，模版如下：
动态规划问题模版：
1.确定dp数组以及下标的含义（这个很重要！！！！）
2.确定递推公式
3.dp数组的初始化
4.确定遍历顺序
5.报错后，针对某一具体测试用例输出dp数组，修改代码
1.建立dp数组vector<int> dp(n, 0)，dp[i]表示以nums[i]结尾的最大子数组和，因此max(dp[0],...,dp[n-1])即为我们所求的答案
2.递推公式为dp[i] = max(nums[i], nums[i] + dp[i-1])
3.dp[0] = nums[0]
4.从1遍历至n-1
举例说明：
以nums = [-2,1,-3,4,-1,2,1,-5,4]为例
代码：
class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 0);if(n == 1) return nums[0];dp[0] = nums[0];int ans = dp[0];for(int i = 1; i < n; i++){dp[i] = max(nums[i], dp[i - 1] + nums[i]);ans = max(ans, dp[i]);}return ans;}
};5.2合并区间（中等）
题目描述：leetcode链接 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].示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路：
1.首先先将intervals排序
2.分析能产生重叠区间的情况
intervals[i-1][1] >= intervals[i][0]时，有重叠区间存在
3.建立vector<vector<int>> result存储最后的输出结果，result.push_back(intervals[0])把intervals[0]存入result中
4.若result.back()[1] >= intervals[i][0] ，则说明存在重叠区间，result.back()[1] = max (result.back()[1], intervals[i][1])；否则result.push_back (intervals[i])
5.遍历完成，返回result
举例说明：
以[[1,3],[8,10],[2,6],[15,18]]为例
代码：
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;sort(intervals.begin(), intervals.end());result.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) {result.back()[1] = max (result.back()[1], intervals[i][1]);}else result.push_back (intervals[i]);}return result;}
};5.3 轮转数组（中等）
题目描述：leetcode链接 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]示例 2:
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
思路：
举例说明：
见上图
代码：
class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();k = k % n;Reverse(nums, 0, n - k -1);Reverse(nums, n - k, n - 1);Reverse(nums, 0, n - 1);}void Reverse(vector<int>& nums, int i, int j) {while (i < j) {swap (nums[i], nums[j]);i++;j--;}}
};5.4 除自身以外数组的乘积（中等）
题目描述：leetcode链接 238. 除自身以外数组的乘积
给你一个整数数组
nums，返回 数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积 。题目数据 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请 不要使用除法，且在
O(n)时间复杂度内完成此题。示例 1:
输入: nums =[1,2,3,4]输出:[24,12,8,6]示例 2:
输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
思路：
1.int n = nums.size() ,vector<int> L(n, 0), R(n, 0), ans(n, 0)
L[i]：nums[i]左侧所有数字的乘积，初始化L[0]=1，从左往右遍历
R[i]：nums[i]左侧所有数字的乘积，初始化R[n-1]=1，从右往左遍历
ans[i]：存储最终的结果，ans[i] = L[i] * R[i]
2.返回ans
举例说明：
以nums=[1,2,3,4]为例
代码：
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> L(n, 0), R(n, 0), ans(n, 0);L[0] = 1;for (int i = 1; i < n; i++) {L[i] = L[i - 1] * nums[i - 1];}R[n - 1] = 1;for (int j = n - 2; j >= 0; j--) {R[j] = R[j + 1] * nums[j + 1];}for (int k = 0; k < n; k++) {ans[k] = L[k] * R[k];}return ans;}
};5.5缺失的第一个正数（困难）
题目描述：leetcode链接 41. 缺失的第一个正数
给你一个未排序的整数数组
请你实现时间复杂度为nums，请你找出其中没有出现的最小的正整数。O(n)并且只使用常数级别额外空间的解决方案。示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
思路：
对于一个未排序的整数数组nums，找出其中的最小正整数，假设nums中的元素有N个
情况1：nums元素均在[1, N]之间，因此返回值为N+1。如nums=[1,2,3,5,4]，返回6
情况2：nums有元素>N或者<=0，返回值必定在[1, N]之间，如[-1,0,2]返回1，[7,8,9]返回1
解决思路：
1.生成含N个元素的对照数组（以N=5为例）
2.对nums进行操作（排序->降重->排序）
若nums中无重复元素，直接排序即可；
若nums中存在重复元素，则需要排序->降重->排序（降重时其中的重复元素令其>N或<=0即可）
3.经操作后的nums与对照数组进行比较，输出缺少的最小正整数
举例说明：
以[0,3,4,-1,9]为例，见上图
代码：
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());for (int i = 1; i < n; i++) {if(nums[i - 1] == nums[i]) nums[i - 1] = -1;}sort(nums.begin(), nums.end());vector<int> compare(n);for (int i = 0; i < n; i++) {path[i] = i + 1;}int j = 0;for (int i = 0; i < n;) {if (nums[i] <= 0) i++;else if (nums[i] == compare[j]) i++, j++;else return j + 1;}return j + 1;}
};