一、最大子数组和

中等

题目：给你一个整数数组 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 <= 10^5
-10^4 <= nums[i] <= 10^4

进阶：

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

1.1 暴力起手（明显超时）

    /**
     * 53. 最大子数组和（暴力）
     * @param nums 提供的数组
     * @return  最大子数组和
     */
	public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            // 如果以非正数开头，除非整个数组都是非正数，否则一定不是答案区间
            if (nums[i] <= 0 && nums[i] > maxSum) {
                maxSum = nums[i];
                continue;
            }
            
            int currentSum = 0;
            for (int j = i; j < nums.length; j++) {
                currentSum += nums[j];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        return maxSum;
    }

1.2 思路优化（双指针）

连续区间扩展收缩，考虑双指针

扩展：不断加入右边界元素nums[right]，更新最大值

收缩：如果加入右边界之后，currentSum < 0，说明nums[right] < 0，不断移除nums[left]直到currentSum > 0

    /**
     * 53. 最大子数组和（双指针）
     * @param nums 提供的数组
     * @return  最大子数组和
     */
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = 0;
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            maxSum = Math.max(maxSum, currentSum);

            while (left <= right && currentSum < 0) {
                currentSum -= nums[left];
                left++;
            }
        }

        return maxSum;
    }

执行用时2ms，击败39.17%，复杂度O(N)

消耗内存75.55MB，击败33.45%，复杂度O(1)

1.3 还能再凹（前缀和）

子数组，考虑用 560. 和为 K 的子数组 ↗的前缀和方法

用最大前缀和减去最小前缀和即可得到答案

❓return maxPrefix - minPrefix;为什么不对

最小前缀和可能出现在最大前缀和之后
参考121. 买卖股票的最佳时机↗，必须先买入股票再卖出
即：必须先更新最大子数组和，再同步更新最小前缀和

    /**
     * 53. 最大子数组和（前缀和）
     * @param nums 提供的数组
     * @return  最大子数组和
     */
	public int maxSubArray(int[] nums) {
        int minPrefix = 0;
        int maxPrefix = nums[0];
        int sum = 0;
        for (int num : nums) {
            sum += num;
            maxPrefix = Math.max(maxPrefix, sum - minPrefix);
            minPrefix = Math.min(minPrefix, sum);
        }
        return maxPrefix;
    }

执行用时1ms，击败100.00%，复杂度O(N)

消耗内存75.89MB，击败14.10%，复杂度O(1)

1.4 官方题解（DP、分治）

    /**
     * 53. 最大子数组和（动态规划）
     * @param nums 提供的数组
     * @return  最大子数组和
     */
	public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }

执行用时1ms，击败100.00%，复杂度O(N)

消耗内存75.77MB，击败20.54%，复杂度O(1)

进阶挑战：方法二：分治↗

二、合并区间

56. 合并区间↗

中等

题目：以数组 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 <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

2.1 暴力起手（差点超时）

可以先把数组按照intervals[i][0]从小到大排列，初始化上一个右边界为last = -1（因为题目注明数组元素非负）

然后从重新遍历排序后的数组，如果：

记intervals[idx - 1][0] = a1, intervals[idx - 1][1] = b1

记intervals[idx][0] = a2, intervals[idx][1] = b2

intervals[i][0] <= last，即：a2 <= b1，区间有重复
- 把区间交集放入答案数组，更新last = ans[idx++][1];
intervals[i][0] > last，即：a2 > b1，区间无重复
- 直接把当前区间放入答案区间，更新last = ans[idx++][1];
最后截去数组末尾的[0, 0]（因为初始定义int[][] ans = new int[intervals.length][2];，合并区间后，ans实际元素个数 < intervals长度），得到答案

    /**
     * 56. 合并区间（暴力）
     * @param intervals 提供的区间数组
     * @return  合并后的数组
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int[][] ans = new int[intervals.length][2];
        int idx = 0;
        int last = -1;
        for (int i = 0; i < intervals.length; i++) {
            if (intervals[i][0] <= last) {
                ans[--idx][1] = Math.max(intervals[i][1], ans[idx][1]);
            } else {
                ans[idx][0] = intervals[i][0];
                ans[idx][1] = intervals[i][1];
            }
            last = ans[idx++][1];
        }
        return Arrays.copyOfRange(ans, 0, idx);
    }

执行用时14ms，击败7.71%，复杂度O(NLogN)

消耗内存48.16MB，击败31.40%，复杂度O(N)

2.2 官方题解（排序）

维度	暴力版 (14ms)	官方题解版 (7ms)	优势
数据结构	固定二维数组	动态 `ArrayList`	更灵活
最终操作	需要 `copyOfRange` 拷贝内存	直接 `toArray`	少一次拷贝
索引逻辑	复杂 (`--idx`)，在 JVM 的优化器看来，这种非顺序的内存访问模式可能不如顺序访问友好	简单 (顺序遍历)	逻辑清晰
内存使用	预分配最大空间，可能浪费	按需分配	更省内存

    /**
     * 56. 合并区间（暴力优化版）
     * @param intervals 提供的区间数组
     * @return  合并后的数组
     */
	public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

执行用时7ms，击败93.78%，复杂度O(NLogN)

消耗内存48.08MB，击败34.07%，复杂度O(N)

三、轮转数组

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 <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

进阶：

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

3.1 拷贝

把最后k个元素拷贝到copy[k]中，待操作完nums后再拷贝回去即可

k %= length，若k >= length，等价于把数组操作完几轮后，再右移动k % length个单位

    /**
     * 189. 轮转数组（拷贝）
     *
     * @param nums 提供的数组
     * @param k    右移步数
     */
    public void rotate(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        if (k == 0) return;
        
        int[] copy = new int[k];
        int i = 0;

        while (i < k) {
            copy[i] = nums[length - k + i];
            i++;
        }

        for (int j = length - k - 1; j >= 0; j--) nums[j + k] = nums[j];
        for (int j = 0; j < k; j++) nums[j] = copy[j];
    }

执行用时1ms，击败51.28%，复杂度O(N)

消耗内存62.02MB，击败8.36%，复杂度O(K)

注意到，前边length - k个元素都移动到了其原来位置再 +k 的位置，最后 k 个位置移动到了数组最前边

数学归纳后，可知：nums新[(i + k) % length] = nums旧[i];（3.3 环状替代前置解释）

    /**
     * 189. 轮转数组（拷贝）
     *
     * @param nums 提供的数组
     * @param k    右移步数
     */
	public void rotate(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        if (k == 0) return;

        int[] copy = new int[length];
        for (int i = 0; i < length; i++) {
            copy[(i + k) % length] = nums[i];
        }
        for (int i = 0; i < length; i++) {
            nums[i] = copy[i];
        }
    }

3.2 翻转

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]

把nums翻转，得到nums_converse = [7, 6, 5, 4, 3, 2, 1]
把nums_converse 前 k = 3 个元素翻转，得到nums_converse = [5, 6, 7, 4, 3, 2, 1]
把nums_converse剩下的元素翻转，得到nums = [5,6,7,1,2,3,4]

    /**
     * 189. 轮转数组（翻转）
     *
     * @param nums 提供的数组
     * @param k    右移步数
     */
    public void rotate(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        if (k == 0) return;

        reverse(nums, 0, length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, length - 1);
    }

    public void reverse(int[] nums, int l, int r) {
        while (l < r) {
            exchange(nums, l++, r--);
        }
    }

    public void exchange(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }

执行用时2ms，击败17.56%，复杂度O(N)

消耗内存60.36MB，击败15.32%，复杂度O(1)

3.3 环状替代

3.3.1 前置解释

问题回顾：

（右移 k）把数组每个元素向右移动 k 位（超过末尾回到前面）
等价把下标 i 的元素搬到(i + k) % n位置

为什么需要“环”？

直接按目标位置搬放会覆盖原数组的值（例如先写覆盖掉后面要用的值）
所以需要一个循环替换（把被覆盖的值暂存，再放到下一个位置），并且数组会被分成若干“环”（cycle），每个环内元素互相替换

为什么用 gcd(k, n)表示环的数量？

gcd = greatest common divisor，最大公约数
映射f(i) = (i + k) % n，重复应用 f 会在某些下标上回到起点，形成一个环（cycle）
- 环的长度等于最小正整数 m 使得 (m * k) % n == 0，即m = n / gcd(n, k)，数学证明如下
  - 每次移动k个单位长度，右移了m次数组后，nums恰好与初始状态一致
  - ∵ (m * k) % n = 0
  - ∴ m * k = n * Z, (Z ∈ N+)
  - 设 n' * gcd(n, k) = n， k' * gcd(n, k) = k
  - ∴ gcd(n', k') = 1①，即它们互质
  - ∴ m * k' = n' * Z
  - ∴ m * k' % n' = 0
  - 由①可知，m % n' = 0
  - ∴ m = n'|min = n / gcd(n, k)
- 因此，数组会被分成 gcd(n, k)个互不相交的环（每个环长度为n / gcd(n,k)）
所以外层循环从 start = 0到 start < gcd(n,k) 启动每个环的替换

3.3.2 算法实现

计算 n = nums.length，做 k = k % n（因为右移 n 次回到原状）。
计算 count = gcd(n, k)。
对每个 start = 0 … count-1：
- 在这个环内做循环替换：用 prev 暂存 start 位置的值，按 next = (current + k) % n 把 prev 放到 next，然后把被覆盖的位置的原值存到 prev，继续移动 current = next，直到回到 start（完成一个环）。
所有环做完，数组被完全旋转。

    /**
     * 189. 轮转数组（环状替代）
     *
     * @param nums 提供的数组
     * @param k    右移步数
     */
    public void rotate(int[] nums, int k) {
        int n = nums.length;
	    k = k % n;
        if (k == 0) return;

        // 环的数量为 gcd(n, k)
        int count = gcd(n, k);

        // 对每个环从 start 开始做循环替换
        for (int start = 0; start < count; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];   // 保存将被覆盖的值
                nums[next] = prev;       // 把 prev 写入目标位置
                prev = temp;             // 更新 prev 为被覆盖位置原值
                current = next;          // 移动到下一个位置
            } while (current != start);  // 完成一个环后停止
        }
    }

    // 迭代版欧几里得算法求最大公约数
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    /* 递归版欧几里得算法求最大公约数
    private int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    } 
    */

执行用时1ms，击败51.20%，复杂度O(N)

消耗内存60.00MB，击败35.88%，复杂度O(1)

❓为什么要做 do...while 而不是 while

第一次要把 start 的元素写到 next，然后循环直到 current 回到 start 为止。

do...while 确保环内至少做一次替换（环长度 >=1），并在回到 start 时停止。

3.3.3 通过例子看流程

学过数据结构的话：与增量为k的希尔排序类似

例 1：nums = [1,2,3,4,5,6,7], n=7, k=3

k % n = 3，gcd(7,3) = 1 → 只有 1 个环，长度为 7。
start = 0：
- current=0, prev=nums[0]=1
- next=(0+3)%7=3；保存 temp=nums[3]=4；写 nums[3]=prev(1)；prev=temp(4)；current=3
  - [1, 2, 3, 1, 5, 6, 7]
- next=(3+3)%7=6；temp=nums[6]=7；nums[6]=4；prev=7；current=6
  - [1, 2, 3, 1, 5, 6, 4]
- next=(6+3)%7=2；temp=nums[2]=3；nums[2]=7；prev=3；current=2
  - [1, 2, 7, 1, 5, 6, 4]
- next=(2+3)%7=5；temp=nums[5]=6；nums[5]=3；prev=6；current=5
  - [1, 2, 7, 1, 5, 3, 4]
- next=(5+3)%7=1；temp=nums[1]=2；nums[1]=6；prev=2；current=1
  - [1, 6, 7, 1, 5, 3, 4]
- next=(1+3)%7=4；temp=nums[4]=5；nums[4]=2；prev=5；current=4
  - [1, 6, 7, 1, 2, 3, 4]
- next=(4+3)%7=0；temp=nums[0]（原已保存）=1；nums[0]=5；prev=1；current=0 → 回到 start，结束。
  - [5, 6, 7, 1, 2, 3, 4]
结果：[5,6,7,1,2,3,4]（正确）

例 2：nums=[1,2,3,4,5,6], n=6, k=2

初始： [1, 2, 3, 4, 5, 6]
- start = 0 的环（位置序列 0 → 2 → 4 → 0）：
  - next = 2, write nums[2] = prev(=1) 结果： [1, 2, 1, 4, 5, 6]
  - next = 4, write nums[4] = prev(=3) 结果： [1, 2, 1, 4, 3, 6]
  - next = 0, write nums[0] = prev(=5) （回到 start，结束该环）结果： [5, 2, 1, 4, 3, 6]
- start = 1 的环（位置序列 1 → 3 → 5 → 1）：（此时数组以上一步结果为当前状态）
  - next = 3, write nums[3] = prev(=2) 结果： [5, 2, 1, 2, 3, 6]
  - next = 5, write nums[5] = prev(=4) 结果： [5, 2, 1, 2, 3, 4]
  - next = 1, write nums[1] = prev(=6) （回到 start，结束该环）结果： [5, 6, 1, 2, 3, 4]
最终： [5, 6, 1, 2, 3, 4]

四、除自身以外数组的乘积

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 <= 10^5
-30 <= nums[i] <= 30
输入保证数组 answer[i] 在 32 位 整数范围内

进阶：

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

4.1 前后缀乘积

对于除自身以外数组的乘积，answer[i] = (answer[0] * answer[1] * ... * answer[i - 1]) * (answer[i + 1] * answer[i + 2] * ... * answer[nums.length - 1])

于是乎，设一个临时变量temp用于存储当前的连乘，左右开头时，temp = 1，因为是要求除自身以外的乘积

第一趟循环，从左向右连乘

第二趟再从右向左连乘即可

    /**
     * 238. 除自身以外数组的乘积
     *
     * @param nums 提供的数组
     * @return	处理后的数组
     */
	public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];
        int temp = 1;
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            temp *= nums[i - 1];
            answer[i] = temp; 
        }

        temp = 1;
        for (int i = length - 2; i >= 0; i--) {
            temp *= nums[i + 1];
            answer[i] *= temp;
        }

        return answer;
    }

执行用时1ms，击败100.00%，复杂度O(N)

消耗内存70.70MB，击败13.34%，复杂度O(1)

五、缺失的第一个正数

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 <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

5.1 原地哈气

可以new一个HashMap，把非负数都塞进去，从小到大，从1开始挨个遍历就能找出来

但是空间复杂度就不为常数了

注意到，对于一个长度为length的数组

假如所有元素都 > length，则缺失的第一个正数就是1
假如所有元素都 <= length，则缺失的第一个正数∈ [1, length + 1]
- 假如nums[i] = i + 1，则缺失的第一个正数为length + 1

原地哈希：利用数组本身作为哈希表

实现方式	说明	示例
正负号标记	用正负表示是否访问过	`nums[index] = -nums[index]`
索引映射	值x放在索引x-1的位置	`nums[nums[i]-1] = nums[i]`
值交换	通过交换把数字放到正确位置	`swap(nums, i, nums[i])`
取模运算	用取模存储额外信息	`nums[i] += n * (nums[nums[i]] % n)`

下面用索引映射的方式实现（官方题解↗同时给出了正负号标记、索引映射2种实现方式）

举例：对于nums = [3,4,-1,1]

nums[0] = 3, 把nums[0] 的值放到 3 - 1= 2，即交换nums[0]与nums[2]
- nums = [-1,4,3,1]
nums[1] = 4, 把nums[1] 的值放到 4 - 1= 3，即交换nums[1]与nums[3]
- nums = [-1,1,3,4]
- nums[1] = 1, 把nums[1] 的值放到 1 - 1= 0，即交换nums[1]与nums[0]
  - nums = [1,-1,3,4]
交换完毕，从头遍历数组，当nums[i] != i + 1时，即是第一个缺失的正数

    /**
     * 41. 缺失的第一个正数
     *
     * @param nums 提供的数组
     * @return 缺失的第一个正数
     */
    public int firstMissingPositive(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            while (nums[i] > 0 && nums[i] <= length && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < length; i++) {
            if (i + 1 != nums[i]) return i + 1;
        }
        return length + 1;
    }

执行用时1ms，击败100.00%，复杂度O(N)

消耗内存69.82MB，击败27.15%，复杂度O(1)

Thanks for reading!

力扣hot100-《普通数组》章节题解

周五 12月 19 2025 普通数组

4439 字 · 24 分钟

algorithm leetcode hot100 array

Yiiyye's Blog

欲买桂花同载酒，终不似，少年游！

力扣hot100-《普通数组》章节题解

一、最大子数组和

1.1 暴力起手（明显超时）

1.2 思路优化（双指针）

1.3 还能再凹（前缀和）

1.4 官方题解（DP、分治）

二、合并区间

2.1 暴力起手（差点超时）

2.2 官方题解（排序）

三、轮转数组

3.1 拷贝

3.2 翻转

3.3 环状替代

3.3.1 前置解释

3.3.2 算法实现

3.3.3 通过例子看流程

四、除自身以外数组的乘积

4.1 前后缀乘积

五、缺失的第一个正数

5.1 原地哈气

力扣hot100-《普通数组》章节题解