解题思路 在 代码注释中！

53. 最大子数组和

class Solution {
public:int maxSubArray(vector<int>& nums) {// 线性DP// f[i] : 以i 结尾 的 最大和的连续子数组， ans = max(f[i])// f[i] = max(f[i] + nums[i], nums[i]);int n = nums.size();// vector<int> f(n, -1e9);// int ans = nums[0];// f[0] = nums[0];// for(int i = 1;i < n;i ++ ){//     f[i] = max(f[i - 1] + nums[i], nums[i]);//     ans = max(ans, f[i]);// }// return ans;// 空间优化 写法int ans = nums[0];int last = nums[0];for(int i = 1;i < n;i ++ ){last = max(last + nums[i], nums[i]);ans = max(ans, last);}return ans;}
};

56. 合并区间

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;int n = intervals.size();// 按 左端点排序, 模拟sort(intervals.begin(), intervals.end());int st = -1e9, ed = -1e9;for(auto &q : intervals){int l = q[0], r = q[1];if(ed < l){if(st != -1e9) res.push_back({st, ed});st =l, ed = r;}else{ed = max(ed, r);}}if(st != -1e9) res.push_back({st, ed});return res;}
};

189. 轮转数组【3次原地 翻转】

class Solution {
public:void rotate(vector<int>& nums, int k) {// 3次翻转 int n = nums.size();k = k % n;reverse(nums,0,n - 1); // 移动k个位置，尾部的k个元素移到前面reverse(nums,0,k - 1);reverse(nums,k,n - 1);}void reverse(vector<int>& nums,int l,int r) // 双指针原地交换{while(l < r){swap(nums[l],nums[r]);l ++ ,r --;}}
};

238. 除自身以外数组的乘积

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {// 原地算法// 前缀 和 后缀int n = nums.size();vector<int> A(n), B(n);for(int i = 0, p = 1;i < n;i ++ ){A[i] = p;p *= nums[i];}for(int i = n - 1, p = 1; i >= 0; i -- ){A[i] *= p;p *= nums[i];}return A;}
};

41. 缺失的第一个正数【交换法】

class Solution {
public:int firstMissingPositive(vector<int>& nums) {// 交换法，时间复杂度O(n),空间复杂度O(1)int n = nums.size();for(int i = 0;i < n;i ++ ){while(nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1])swap(nums[i],nums[nums[i] - 1]);}for(int i = 0;i < n;i ++ )if(nums[i] != i + 1) return i + 1;return n + 1;}
};