---

前言

本文记录力扣Hot100里面关于普通数组的三道题，包括常见解法和一些关键步骤理解，也有例子便于大家理解

---

一、最大子数组和

1.题目

给你一个整数数组 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

2.代码

步骤就不说了，比较简短

class Solution {
    public int maxSubArray(int[] nums) {
        // 1. 初始化 dp 变量（空间优化）
        int dp = 0;
        // 2. 初始化最大和为整数最小值（避免全负数的情况）
        int maxsum = Integer.MIN_VALUE;
        
        // 3. 遍历数组中的每个元素
        for(int num: nums){
            // 3.1 核心：状态转移（空间优化版）
            dp = Math.max(dp + num, num);
            // 3.2 更新全局最大和
            if(dp > maxsum){
                maxsum = dp;
            }   
        }
        // 4. 返回最终结果
        return maxsum;  
    }
}

3.核心思路----动态规划

最大子数组和的核心问题：以第 i 个元素结尾的最大子数组和，只有两种选择：

1. 把第 i 个元素加入前一个子数组（即 dp[i-1] + nums[i]）；
   （即作为前面一个子数组的结尾）
2. 以第 i 个元素重新开始一个子数组（即 nums[i]）。
   （其实就是自己作为一个子数组，这样也是结尾）
   因此状态转移方程为：
   dp[i] = max(dp[i-1] + nums[i], nums[i])

而最终答案是所有 dp[i] 中的最大值。

用例子解释一下：
比如有一串数字：[-2, 1, -3, 4, -1, 2]，逐个看 “以每个元素结尾的最优子数组”：
以 -2 结尾：只能自己 → [-2]，和为 -2；
以 1 结尾：延续前序（-2+1=-1）不如重启（1）→ [1]，和为 1；
以 -3 结尾：延续前序（1-3=-2）比重启（-3）优 → [1,-3]，和为 -2；
以 4 结尾：延续前序（-2+4=2）不如重启（4）→ [4]，和为 4；
以 -1 结尾：延续前序（4-1=3）比重启（-1）优 → [4,-1]，和为 3；
以 2 结尾：延续前序（3+2=5）比重启（2）优 → [4,-1,2]，和为 5；
最终全局最大值是 5。

看到这里有没有疑问，那就是为什么要关注“以 i 结尾”？

1.连续子数组的约束，只能通过 “结尾” 关联前后

子数组必须是连续的，比如想算 nums[i] 结尾的最优子数组，它只有两种可能：要么接在 nums[i-1] 结尾的子数组后面，要么自己单独成一个。这种关联关系特别明确，不用瞎猜，直接用 max(前面的结果+nums[i], nums[i]) 就能算。

要是不锚定结尾，比如直接算 “前 i 个元素的最大子数组和”，我们根本不知道这个最优子数组包不包含 nums[i]—— 可能在前面，可能包含 nums[i]，得枚举一堆情况，越算越乱。

2.全局最优解，就是所有 “结尾最优” 里的最大值

任何一个子数组，总得有个结尾的位置。还是前面的例子，比如子数组 [4,-1,2] 结尾是 2（对应 i=5），子数组 [4] 结尾是 4（对应 i=3）。所以只要算出每个位置 i 结尾的最优解，再从里面挑个最大的，就是答案了。

4.关键步骤

 int maxsum = Integer.MIN_VALUE;

这里是为什么？
避免数组全为负数的情况（比如 nums = [-3, -1, -2]），如果初始化为 0，会错误返回 0 而非 -1。

还是举个例子：
假设代码把 maxsum 初始化为 0，数组是 nums = [-3, -1, -2]，我们一步步走执行流程：

此时全负数数组的最大子数组和是「数组中最大的那个负数」（这里是 -1），但因为 maxsum 初始值是 0，而所有 dp（-3、-1、-2）都小于 0，导致 maxsum 始终没被更新，最终错误返回 0。

dp = Math.max(dp + num, num)

• dp + num：把当前元素加入前一个子数组；
• num：以当前元素重新开始子数组；
• 取两者最大值，即为“以当前元素结尾的最大子数组和”。
  举个例子：
• 若前一个 dp = 5，当前 num = 3 → 5+3=8 > 3 → dp=8（延续子数组）；
• 若前一个 dp = -2，当前 num = 3 → -2+3=1 < 3 → dp=3（重新开始子数组）。

5.示例

以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例

二、合并区间

1.题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start(i), end(i)] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 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] 可被视为重叠区间。

2.代码

步骤：

1. 判断是不是空数组，是的话返回空
2. 将每个区间的左端点进行比较，按照从小到大排序（用「匿名内部类」的写法（相当于临时创建一个 Comparator 接口的实现类），核心是实现 compare 方法）
3. 初始化一个结果List集合
4. 遍历所有区间，并逐个合并
   A. 先提取当前区间的左，右端点
   B. 再进行合并，如果结果集合为空 或 当前遍历到的区间与结果集合最后一个区间不重叠 → 直接加入结果集合
   但如果有重叠，则需要进行合并，左端点不变，取两个区间右端点的最大值作为合并区间的右端点。
5. 最后将List集合转换为二维数组。

class Solution {
    public int[][] merge(int[][] intervals) {
        // 1. 边界处理：空数组直接返回空结果
        if (intervals.length == 0) {
            return new int[0][2];
        }

        // 2. 按区间左端点升序排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });

        // 3. 初始化合并结果列表（动态数组，方便增删）
        List<int[]> merged = new ArrayList<int[]>();

        // 4. 遍历所有区间，逐个合并
        for (int i = 0; i < intervals.length; ++i) {
            // 提取当前区间的左、右端点
            int L = intervals[i][0], R = intervals[i][1];

            // 5. 合并逻辑：
            // 情况1：结果列表为空，或当前区间与最后一个合并区间不重叠 → 直接加入
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } 
            // 情况2：当前区间与最后一个合并区间重叠 → 合并（更新右端点）
            else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }

        // 6. 将List转换为二维数组返回（ArrayList → int[][]）
        return merged.toArray(new int[merged.size()][]);
    }
}

3.关键步骤

  Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });

先搞懂 Arrays.sort() 的两种用法
Arrays.sort() 是 Java 数组排序的工具方法，有两种核心场景：

1. 默认排序：比如 Arrays.sort(int[] arr)，对一维 int 数组按「升序」排（基于元素自身的大小）；
2. 自定义排序：比如 Arrays.sort(数组, 比较器)，对非基本类型数组（比如 int[] 这种引用类型），按「比较器指定的规则」排

关于第二个参数
这是 Java 中「匿名内部类」的写法（没有给类起名字，直接创建接口实现类的对象），拆解来看：

1. Comparator<int[]>：接口声明
   Comparator 是一个泛型接口，<int[]> 表示：这个比较器是用来比较「int[] 类型的对象」的（因为我们要排序的数组元素是 int[] 区间）。

2. public int compare(int[] interval1, int[] interval2)：核心方法
   Comparator 接口要求必须实现 compare 方法，这个方法的作用是定义两个元素的比较规则，返回值直接决定排序结果：
   

3. return interval1[0] - interval2[0]：具体比较逻辑
   interval1[0]：第一个区间的左端点（比如 interval1 = [2,6]，则 interval1[0] = 2）；
   interval2[0]：第二个区间的左端点（比如 interval2 = [1,3]，则 interval2[0] = 1）；

核心：用「第一个区间左端点 - 第二个区间左端点」的结果，决定区间的排序顺序 —— 本质是按「左端点升序」排列。

Arrays.sort(intervals, (interval1, interval2) -> interval1[0] - interval2[0]);

上面是用lambda表达式进行简化。

  // 5. 合并逻辑：
 // 情况1：结果列表为空，或当前区间与最后一个合并区间不重叠 → 直接加入
 if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
	merged.add(new int[]{L, R});
	} 
// 情况2：当前区间与最后一个合并区间重叠 → 合并（更新右端点）
 else {
	merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
	}

进行合并，如果结果集合为空 或 当前遍历到的区间与结果集合最后一个区间不重叠 → 直接加入结果集合
但如果有重叠，则需要进行合并，左端点不变，取两个区间右端点的最大值作为合并区间的右端点。

一定要注意区别当前遍历的区间和已经加入结果集合的最后一个区间，主要就是比较这两个有没有重叠！！！（比较结果集合最后一个区间的右端点和当前区间的左端点）
如果有重叠，记得左端点保持不变，更新右端点较大的一个！！！

4.示例

输入：[[1,3],[2,6],[8,10],[15,18]]

1. 排序后：还是 [[1,3],[2,6],[8,10],[15,18]]（左端点已升序）。
2. 遍历第1个区间 [1,3]：merged 为空 → 直接加入，merged = [[1,3]]。
3. 遍历第2个区间 [2,6]：merged 最后一个区间右端点 3 ≥ 2（重叠）→ 右端点更新为 max(3,6)=6，merged = [[1,6]]。
4. 遍历第3个区间 [8,10]：merged 最后一个右端点 6 < 8（无重叠）→ 加入，merged = [[1,6],[8,10]]。
5. 遍历第4个区间 [15,18]：merged 最后一个右端点 10 < 15（无重叠）→ 加入，merged = [[1,6],[8,10],[15,18]]。
6. 转换为二维数组返回，结果符合预期。

三、轮转数组

1.题目

给定一个整数数组 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]

2.代码

步骤较短，没什么好说的，就不总结了啦

public void rotate(int[] nums, int k) {
    // 步骤1：处理k大于数组长度的情况，取模得到有效旋转次数
    k %= nums.length;
    // 步骤2：反转整个数组
    reverse(nums, 0, nums.length - 1);
    // 步骤3：反转前k个元素
    reverse(nums, 0, k - 1);
    // 步骤4：反转从k到末尾的元素
    reverse(nums, k, nums.length - 1);
}

public void reverse(int[] nums, int start, int end) {
    // 双指针：start从左往右，end从右往左，交换元素直到相遇
    while (start < end) {
        // 交换nums[start]和nums[end]
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        // 指针向中间移动
        start += 1;
        end -= 1;
    }
}

3.关键步骤

注意传给reverse函数的参数就行了（看下面的例子就理解了），最后在reverse函数中不要忘了加while循环！

先看主方法

步骤1：k %= nums.length;

• 作用：消除无效的旋转次数（旋转 nums.length 次相当于没旋转）。
• 示例：nums.length=7，k=10 → 10%7=3，只需旋转 3 次；若 k=7 → 7%7=0，无需旋转（后续三次反转相当于没操作）。

步骤2：reverse(nums, 0, nums.length - 1)

• 反转整个数组，比如 [1,2,3,4,5,6,7] → 反转后 [7,6,5,4,3,2,1]。

步骤3：reverse(nums, 0, k - 1)

• 反转前 k 个元素（此时 k=3），即反转 [7,6,5] → 变成 [5,6,7]，数组变为 [5,6,7,4,3,2,1]。

步骤4：reverse(nums, k, nums.length - 1)

• 反转从 k 到末尾的元素（即 [4,3,2,1]）→ 变成 [1,2,3,4]，最终数组 [5,6,7,1,2,3,4]，符合预期。

再看reverse函数

以翻转[1,2,3,4,5,6,7]为例

第 1 轮循环
判定条件：start=0，end=6，0 < 6，满足循环条件；
交换前状态：数组为 [1,2,3,4,5,6,7]，当前操作的指针是 start=0（指向元素 1）、end=6（指向元素 7）；
交换操作：先定义临时变量 temp，将 nums [0] 的值赋值给 temp（temp = 1）；再把 nums [6] 的值赋值给 nums [0]（nums [0] = 7）；最后把 temp 的值赋值给 nums [6]（nums [6] = 1）；
交换后数组：[7,2,3,4,5,6,1]；
指针移动后：start 加 1 变为 1，end 减 1 变为 5。
第 2 轮循环
判定条件：start=1，end=5，1 < 5，满足循环条件；
交换前状态：数组为 [7,2,3,4,5,6,1]，当前操作的指针是 start=1（指向元素 2）、end=5（指向元素 6）；
交换操作：定义临时变量 temp，将 nums [1] 的值赋值给 temp（temp = 2）；再把 nums [5] 的值赋值给 nums [1]（nums [1] = 6）；最后把 temp 的值赋值给 nums [5]（nums [5] = 2）；
交换后数组：[7,6,3,4,5,2,1]；
指针移动后：start 加 1 变为 2，end 减 1 变为 4。
第 3 轮循环
判定条件：start=2，end=4，2 < 4，满足循环条件；
交换前状态：数组为 [7,6,3,4,5,2,1]，当前操作的指针是 start=2（指向元素 3）、end=4（指向元素 5）；
交换操作：定义临时变量 temp，将 nums [2] 的值赋值给 temp（temp = 3）；再把 nums [4] 的值赋值给 nums [2]（nums [2] = 5）；最后把 temp 的值赋值给 nums [4]（nums [4] = 3）；
交换后数组：[7,6,5,4,3,2,1]；
指针移动后：start 加 1 变为 3，end 减 1 变为 3。
第 4 轮循环
判定条件：start=3，end=3，3 < 3 不成立，不满足循环条件；
操作：循环直接终止，反转过程结束。

4.示例（结合前面看）

输入：nums = [1,2,3,4,5,6,7]，k = 3

1. k %= 7 → k=3；
2. 反转整个数组：[1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]；
3. 反转前 3 个元素（0~2）：[7,6,5] → [5,6,7]，数组变为 [5,6,7,4,3,2,1]；
4. 反转 3~6 位置的元素：[4,3,2,1] → [1,2,3,4]，最终数组 [5,6,7,1,2,3,4]。

---

如果本篇文章对您有帮助，可以点赞，收藏或评论哦！！！关注主包不迷路，让我们一起向前进步吧！！！