普通数组

---

53. 最大子数组和

// 动态规划，前缀和如果没有变为负，就继续使用，否则更新为0，确保子数组以非负数开始计数
class Solution {
    public int maxSubArray(int[] nums) {
        int ans = 0x80000000, sum = 0;
        for(int num : nums){
            sum += num;
            ans = Math.max(ans, sum);
            sum = Math.max(sum, 0);
        }

        return ans;
    }
}

//官解也不错：
class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

56. 合并区间

public class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 左端点排序
        List<int[]> ans = new ArrayList<>();
        for (int[] cur : intervals) {
            int n = ans.size();
            if (n > 0 && cur[0] <= ans.get(n - 1)[1]) {
                ans.get(n - 1)[1] = Math.max(ans.get(n - 1)[1], cur[1]);  // <= 即可合并
            } else {
                ans.add(cur);                         // 无法合并
            }
        }
        return ans.toArray(new int[ans.size()][]); // list转为数组
    }
}

189. 轮转数组

// 记住翻转数组的方法，---->-->翻转<--<----，然后分别翻转两段-->---->；一定记得k要取余
// 环状替换的方法需要计算最大公约数
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length);
        reverse(nums, 0, k);
        reverse(nums, k, nums.length);
    }

    public void reverse(int[] nums, int start, int end) {
        int temp;
        for (int i = start, j = end - 1; i < j; i++, j--) {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}

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

// 左边前缀积，右边前缀积
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0, cur = 1; i < nums.length; i++) {
            ans[i] = cur;
            cur *= nums[i];
        }
        for (int i = nums.length - 1, cur = 1; i >= 0; i--) {
            ans[i] *= cur;
            cur *= nums[i];
        }

        return ans;
    }
}