前缀和+贪心算法

 class Solution {
     public int maxSubArray(int[] nums) {
         int preSum = 0;
         int minPreSum = 0;
         int res = Integer.MIN_VALUE;
         for(int i = 0;i < nums.length;i++){
             preSum += nums[i];
             res = Math.max(res,preSum-minPreSum);
             minPreSum = Math.min(preSum,minPreSum);
         }
         return res;
     }
 }

动态规划

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

合并区间

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

轮转数组

 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);
     }
     public void reverse(int[] nums,int left,int right){
         while (left < right){
             int tmp = nums[left];
             nums[left] = nums[right];
             nums[right] = tmp;
             left++;
             right--;
         }
     }
 }

除自身以外数组的乘积

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

缺失的第一个正数

• nums[i] > 0 && nums[i] < len && nums[nums[i]-1] != nums[i]

• 这个很关键，尤其是 nums[nums[i]-1] != nums[i]，为什么不是 nums[i]-1 != i

• nums[i]-1 != i 这是将当前数和下标进行比较，来判断是否在正确位置，但是！如果是影子分身怎么办

• nums[nums[i]-1] != nums[i] 这个比较的是当前数和正确位置的数进行比较，如果相等，说明是影子分身，如果不相等，可以是没有影子分身，或者有但是是第一次，那第二次还是一样的

 class Solution {
     public int firstMissingPositive(int[] nums) {
         int len = nums.length;
         for(int i = 0;i < len;i++){
             while (nums[i] > 0 && nums[i] < len && nums[nums[i]-1] != nums[i]){
                 swap(nums,nums[i]-1,i);
             }
         }
 ​
         for(int i = 0;i < len;i++){
             if(nums[i] != i+1){
                 return i+1;
             }
         }
         return len+1;
     }
 ​
     private void swap(int[] nums,int index1,int index2){
         int tmp = nums[index1];
         nums[index1] = nums[index2];
         nums[index2] = tmp;
     }
 }