53.最大子数组和

https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked
给你一个整数数组 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 <= nums.length <= 105
-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

思考

暴力解法，双重循环，时间复杂度O(n^2)。中间很多重复
考虑动态规划。状态i为当前起点索引，dp[i]为以i索引为起点的最大子数组的和。dp[i] = dp[i-1]-nums[i-1],满足最优子结构，转移顺序从左侧开始即可。显然填满dp表耗时O(n).边界条件：dp[0]先算出来。尝试实现

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            dp[0] = Math.max(dp[0],sum);
        }
        int result = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = dp[i-1] - nums[i - 1];
            result = Math.max(dp[i],result);
        }
        return result;
    }
}

上面的方法是错误的！！！！！

状态转移方程，如果dp[i-1]没有包含i-1后面的数，那么这个方程错误。dp[i-1]无法提供任何信息。因此失效。无法判断dp[i-1]是否包含了i-1之后的元素。需要引入一个新的变量，这样的复杂度会成为O(n^2)

正确的状态定义是，定义i为结束的索引，dp[i] = max(dp[i-1] + nums[i],nums[i])

还是从左向右转移。dp[0] = nums[0]。

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            result = Math.max(dp[i],result);
        }
        return result;
    }
}

滚动优化，显然我们每次只需知道dp[i-1]

class Solution {
    public int maxSubArray(int[] nums) {
        int dp_i_1 = nums[0];
        int result = dp_i_1;
        int dp_i ;
        int temp;
        for (int i = 1; i < nums.length; i++) {
            dp_i = Math.max(dp_i_1 + nums[i],nums[i]);
            result = Math.max(dp_i,result);
            dp_i_1 = dp_i;
        }
        return result;
    }
}

时间复杂度O(n),空间复杂度O(1)

下面思考分治法

定义操作get(a,l,r),查询a序列在[l,r]的最大子段和，原问题即为：get(nums,0,nums.length - 1)

取m = (l+r)/2，对[l,m][m+1,r]分段递归

当递归深入到区间长度为1，开始回升。

关键在于如何通过[l,m]和[m+1,r]来合并[l,r]

需要明确两点：

维护区间哪些信息
如何合并信息

对于[l,r]维护四个量

lSum，以l为端点的最大子段和
rSum，以r为右端点的最大子段和
maxSum，最大子段和
iSum，区间和

如何通过两个子区间来维护？

显然长度为一的区间，四个值都是唯一的元素的值

大于1的时候：

iSum就是iSumLeft+ iSumRight
lSum，两种可能：
- 等于lSumLeft
- iSumLeft + lSumRgiht
- 两者取最大
rSum
- rSumRight
- iSumRight + rSumLeft
maxSum：
- 跨越m:rSumLeft + lSumRight
- 跨越：max(maxSumLeft,maxSumRight)

class Solution {
    public class Status {
        int iSum, lSum, rSum, maxSum;

        public Status(int iSum,int lSum,int rSum,int maxSum) {
            this.iSum = iSum;
            this.lSum = lSum;
            this.rSum = rSum;
            this.maxSum = maxSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getMaxSum(nums, 0, nums.length - 1).maxSum;
    }

    private Status getMaxSum(int[] a, int left, int right) {
        if (left == right){
            int temp = a[left];
            return new Status(temp,temp,temp,temp);
        }
        int m = left + (right- left) / 2;
        Status L = getMaxSum(a,left,m);
        Status R = getMaxSum(a,m + 1,right);
        return PushUp(L,R);
    }
    
    private  Status PushUp(Status L,Status R){
        int iSum = L.iSum + R.iSum;
        int lSum = Math.max(L.lSum, L.iSum + R.lSum);
        int rSum = Math.max(R.rSum,L.rSum + R.iSum);
        int maxSum = Math.max(Math.max( L.maxSum,R.maxSum),L.rSum + R.lSum);
        return new Status(iSum,lSum,rSum,maxSum);
    }
}

时间复杂度：递推式：T(n) = 2T(n/2) + O(1)，由主定理O(N).也可以递归树，高度logn，相当于对每个节点执行一次O(1)pushUp操作，节点数2^0 + 2^1 + … + 2^logn = 2n - 1 = O(n)
空间复杂度O(logn),递归栈深度

前缀和法
对于从i到j的数组，其和实际上就是pre[j] - pre[i-1].在固定j的时候，求最大值就是求pre[i-1] (贪心策略)，贪心的正确性是显然的。

每次遍历，维护min_pre,preCur,result.，可以认为pre[-1] = 0.

class Solution {
    public int maxSubArray(int[] nums) {
      int min_pre = 0;//认为pre[-1]为0
      int preCur = 0;
      int result = Integer.MIN_VALUE;
      for (int i = 0; i < nums.length; i++) {
        preCur += nums[i];
        result = Math.max(result,preCur - min_pre);
        min_pre = Math.min(preCur,min_pre);// 注意必须在更新result后更新结果！min_pre要确保是cur前面的最小的，不应该和precur重合
      }
      return result;
      
    }
}

合并区间

https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
以数组 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] 可被视为重叠区间。
示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

思考：先按照每个区间的大的数进行升序排序，之后依次遍历即可。复杂度O(nlogn)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
  public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (int[] a, int[] b) -> a[1] - b[1]);
    List<List<Integer>> resultList = new ArrayList<>();
    for (int i = 0; i < intervals.length - 1; i++) {
      if (intervals[i][1] >= intervals[i + 1][0]) {
        resultList.add(new ArrayList<>({intervals[i][0],intervals[i+1][1]}));
      }
    }
  }
}

上面思路整体接近但实现卡壳。但最好来说是按照区间起始位置排序更好。[1,9],[5,6],[0,4],[10,11]，如果按照结束位置会是，[0,4],[5,6],[1,9],[10,11],但是按照起始位置是[0,4],[1,9],[5,6],[10,11]，虽然实际上都可以，但为了方便从左向右遍历，我们最好按照起始元素排序

同时对于具体实现，先把首个区间加入链表，之后如果有重叠就修改上一个区间的右边界（因为按照左边界的排序，左边界一定不用动）

class Solution {
  public int[][] merge(int[][] intervals) {
      if (intervals.length == 0){
          return new int[0][2];
      }
      Arrays.sort(intervals, (int[] a, int[] b) -> a[0] - b[0]);
      List<int[]> resultList = new ArrayList<>();
      resultList.add(intervals[0]);
      for (int i = 1; i < intervals.length; i++) {
  
        if (intervals[i][0] <= resultList.get(resultList.size() - 1)[1]){
          resultList.get(resultList.size() - 1)[1] = Math.max(intervals[i][1],resultList.get(resultList.size() - 1)[1]);
        }else {
          resultList.add(intervals[i]);
        }
      }
      return resultList.toArray(new int[][]{});
    }
}

时间复杂度O(nlogn),空间复杂度O(n)

注意，List转换为int[]只能遍历或者stream，但转换为Integer[]不必，直接调用方法传入长度为0的数组即可。

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]

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

思考

一个简单的想法就是依次遍历向后移动，(i+k)%nums.length，同时要用数组记录被覆盖的那个数并且维护一个布尔数组表示索引处是否被交换过,时间O(n)空间O(n)

更好的方法是使用额外数组。把原本的数组直接按照(i+k)%nums.length复制到新数组里面，最后再把新数组复制回来。时空复杂度都是O(n)

下面是O(n)O(1)解法

数组翻转
先把数组分为两部分，前n-k个，记为A，后k个，记为B，原本数组是A+B,显然我们的目标是转换成B+A。先进行一次整体翻转，成为rev(B)+rev(A),再分别对BA反转，成为B+A

class Solution {
    public void rotate(int[] nums, int k) {
        k = k% nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
        return;
    }
    private int[] reverse(int[] nums,int left,int right){
        if (nums.length <= 1){
            return nums;
        }
        int temp;
        while (left < right){
            temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
            left++;
            right--;
        }
        return nums;
    }
}

时间复杂度O(n)

环状替换

第一次冲0开始，把next_index = (0+k)%nums.length和他互换，使用temp储存被替换的值，之后开始把next_index（值存到了temp里面）和(next_index+k)%nums.length互换，存值，重复。直到回到起点。

但这样，一次遍历其实不一定能够遍历所有元素进行互换。

假设一共跑了a圈，则总路程是an；假设跳跃了b次（b个元素被替换），路程是bk。则an=bk,显然总路程要最小也就是lcm(n,k).则b = lcm(n,k)/k,那么就要循环n/b = (nk)/lcm(n,k)= gcd(n,k)次

也可以抛开数论，引入一个变量count记录被替换的数目，当count = n时停止

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        
        // 处理 k=0 的边界情况，避免不必要的循环
        if (k == 0) {
            return;
        }

        int count = 0; // 记录已归位的元素数量
        
        // for 循环结构更清晰地表达了“为每个环寻找起点”的意图
        // 只要还没处理完 n 个元素，就从下一个 start 开始尝试
        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start]; // prev 在每个新环开始时初始化

            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++; // 每归位一个元素，计数器加一
            } while (start != current); // 当回到环的起点时，内层循环结束
        }
    }
}

时间复杂度：遍历了每个元素执行了O(1)的替换。因此是O(n)

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]

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
输入保证数组 answer[i] 在 32 位整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

没写出来

前缀和

可以利用前缀和和后缀和。answer[i] 其实就是i左侧的乘积，乘上i右侧的乘积

定义pre[i],0到i - 1的乘积

suf[i],i+1到length - 1的乘积

则有pre[i] = nums[i-1]*pre[i-1];suf[i] = suf[i+1]*nums[i+1]。pre[0]=1，suf[length]=1.

answer[i] = pre[i] * suf[i]

时间复杂度O(n),空间复杂度O(n)

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] pre = new int[nums.length];
        int[] suf = new int[nums.length];
        int[] answer = new int[nums.length];
        pre[0] = 1;
        suf[nums.length-1] = 1;
        for (int i = 1;i < nums.length;i++){
            pre[i] = pre[i-1]*nums[i-1];
        }
        for (int i = nums.length-2;i >= 0;i--){
            suf[i] = suf[i+1]*nums[i+1];
        }
        for (int i = 0;i < nums.length;i++){
            answer[i] = pre[i] * suf[i];
        }
        return answer;
    }
}

优化空间复杂度为O(1),pre可以随时储存，只存取需要的，suf无法，可以直接把suf算出来然后作为answer的空间，把随时算出来的answer直接覆盖suf

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int pre = 1;
        int[] answer = new int[nums.length];
        answer[nums.length-1] = 1;
        for (int i = nums.length-2;i >= 0;i--){
            answer[i] = answer[i+1]*nums[i+1];
        }
        answer[0] = answer[0]*pre;
        for (int i = 1; i < nums.length;i++){
            //此时pre表示的就是pre[i-1]
          pre = pre*nums[i-1];
          answer[i] = answer[i] * pre;
        }
        return answer;



    }
}

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 没有出现。

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1

思考
核心思路是把每个值在1到n的元素放到对应的索引处(例如1对应索引0，2对应索引1等)。（把每个元素看成学生，每个元素的值看成学号，把每个学生放到对应的位置，理解时可以把数组看作从1开始计数，但实现时必须还原）

这样的话从左遍历，遇到第一个和索引不匹配的位置，该索引应当对应的数即为答案。如果所有位置都有正确的元素，那么返回length+1

但有一些细节：

重复元素，如[1,1,2]，可以把第二个1看作第一个1的分身，只要真身在正确的位置就认为是达到了目的，索引0和1换位永远不满足：因此不适用nums[i] - 1== i判断是否对应，

使用nums[i] （当前元素对应的学号）== nums[nums[i]-1（当前元素学号对应的索引）]（当前元素学号对应的索引的元素的学号）来判断。只要这个成立，真身是正确位置；如果不满足，左侧nums[i]是当前学生的学号，右边是要被交换的学生的学号。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 如果当前学生的学号在 [1,n] 中，但（真身）没有坐在正确的座位上
            while (1 <= nums[i] && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                // 那么就交换 nums[i] 和 nums[j]，其中 j 是 i 的学号对应的索引
                int j = nums[i] - 1; // 减一是因为数组下标从 0 开始
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }

        // 找第一个学号与座位编号不匹配的学生
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 所有学生都坐在正确的座位上
        return n + 1;
    }
}

上面的题解不好理解。可以放弃不看

下面是好理解的。

哈希

实际上一种想法是把数组的所有元素放入哈希集合，然后依次从1 开始枚举。这样时空都是O(n)。真正时间O(n)空间O(1)不存在，但是如果可以修改原数组的话可以认为存在

可以把原数组当作哈希表使用

答案只可能在[1,N+1]范围内。因为如果1到N每个都有，那么答案是N+1;如果存在比N+1大的数，那么必然在[1,N]中缺失一个数

我们对数组遍历，遍历到了x，如果在[1,N]内，就把第n-1个位置打上[标记]。显然，如果所有位置被标记答案就是N+1,否则就是第一个没标记的位置+1.

关键在于标记设计。

因为我们只在意[1,N]的数，因此我们可以把所有不在[1,N]的数改成任意一个大于N 的数，比如N+1.之后数组只有正数，因此可以使用[负号]标记

但是标记的时候注意，不能丢失被标记位置的原本的值，因为这个位置我们可能还没有遍历到进行处理。

因此可以采用-|x|标记，对被标记位置的元素的绝对值取相反数

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0;i < nums.length;i++){
            if (nums[i] <= 0){
                nums[i] = nums.length + 1;
            }
        }
        for (int i = 0;i < nums.length;i++){
            int nums_i_abs = Math.abs(nums[i]);
            if (nums_i_abs <= nums.length && nums_i_abs >= 1){
                nums[nums_i_abs - 1] = -Math.abs(nums[nums_i_abs - 1]);
            }
        }
        for (int i = 0;i < nums.length;i++){
            if (nums[i] > 0){
                return i+1;
            }
        }
        return nums.length + 1;
    }
}

置换（实际上就是最开始灵神的解法，但下面更好理解）

想办法恢复。恢复后数组应当有[1,2……N]的形式，但有一些是错误的，错误的就代表缺失

遍历到x = nums[i],如果x在[1,N],x应当出现在x-1处，交换nums[i] 和nums[x-1],x就出现在了正确位置。新的nums[i]可能还在范围内，因此继续交换直到不在

如果出现重复，x = nums[i]和nums[x-1]一样,这说明x已经出现在正确的位置。可以跳出循环遍历下一个

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0;i < nums.length;i++){
            while (nums[i] >= 1 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]){
                int x = nums[i];
                nums[i] = nums[x-1];
                nums[x-1] = x;
            }
        }
        for (int i = 0;i < nums.length;i++){
            if (nums[i] != i+1){
                return i+1;
            }
        }
        return nums.length + 1;
    }
}

空间复杂度不考虑输入数组的话是O(1)
时间复杂度O(n)(第一个for循环) + O(n)一共n次交换 + O(n)第二次循环。最终是O(n)