跳到主要内容

数组算法练习

数组是最基础的数据结构，但数组相关的题目却涵盖了各种算法技巧。本章节涉及的题目包括前缀和、区间合并、原地置换等经典技巧。

数组题目的特点是：看似简单，但往往有巧妙的优化空间。暴力解法容易想到，但想要达到最优的时间和空间复杂度，需要深入理解问题的本质。

53. 最大子数组和 (Maximum Subarray)​

题目描述​

给你一个整数数组 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²)。但有一个经典的 O(n) 解法——Kadane 算法。

方法：Kadane 算法（动态规划）​

核心思想是：遍历数组时，对于每个位置，我们维护两个值：

  • currentSum：以当前元素结尾的最大子数组和
  • maxSum：全局最大子数组和

对于每个元素 nums[i]，我们有两个选择：

  1. 将 nums[i] 加入之前的子数组（currentSum + nums[i]）
  2. 从 nums[i] 开始一个新的子数组（nums[i]）

我们选择较大的那个作为新的 currentSum。这可以理解为：如果之前的 currentSum 是负数，它只会拖累后面的元素，不如重新开始。

图解示例​

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

初始状态：
currentSum = -2, maxSum = -2

i=1, nums[1] = 1:
  选择：max(-2+1, 1) = max(-1, 1) = 1
  currentSum = 1, maxSum = max(-2, 1) = 1
  
i=2, nums[2] = -3:
  选择：max(1+(-3), -3) = max(-2, -3) = -2
  currentSum = -2, maxSum = max(1, -2) = 1
  
i=3, nums[3] = 4:
  选择：max(-2+4, 4) = max(2, 4) = 4
  currentSum = 4, maxSum = max(1, 4) = 4
  
i=4, nums[4] = -1:
  选择：max(4+(-1), -1) = max(3, -1) = 3
  currentSum = 3, maxSum = max(4, 3) = 4
  
i=5, nums[5] = 2:
  选择：max(3+2, 2) = max(5, 2) = 5
  currentSum = 5, maxSum = max(4, 5) = 5
  
i=6, nums[6] = 1:
  选择：max(5+1, 1) = max(6, 1) = 6
  currentSum = 6, maxSum = max(5, 6) = 6
  
i=7, nums[7] = -5:
  选择：max(6+(-5), -5) = max(1, -5) = 1
  currentSum = 1, maxSum = max(6, 1) = 6
  
i=8, nums[8] = 4:
  选择：max(1+4, 4) = max(5, 4) = 5
  currentSum = 5, maxSum = max(6, 5) = 6

最终结果：6
对应的子数组：[4, -1, 2, 1]

Java 代码实现​

class Solution {
    public int maxSubArray(int[] nums) {
        // 初始化为第一个元素
        int currentSum = nums[0];
        int maxSum = nums[0];
        
        // 从第二个元素开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 选择：继续之前的子数组，还是从当前元素重新开始
            // 如果 currentSum < 0，则重新开始
            currentSum = Math.max(currentSum + nums[i], nums[i]);
            
            // 更新全局最大值
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

复杂度分析​

时间复杂度：O(n)，只需遍历数组一次。

空间复杂度：O(1)，只使用了两个变量。

为什么贪心策略有效？​

这道题可以用动态规划来理解。定义 dp[i] 为以 nums[i] 结尾的最大子数组和。

状态转移方程：

dp[i] = max(dp[i-1] + nums[i], nums[i])

解释：

  • 如果 dp[i-1] > 0，加上 nums[i] 会让和更大
  • 如果 dp[i-1] <= 0，不如从 nums[i] 重新开始

由于 dp[i] 只依赖于 dp[i-1]，我们可以用滚动变量优化空间。

相关题目​

56. 合并区间 (Merge Intervals)​

题目描述​

以数组 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] 可被视为重叠区间。

约束条件：

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

解题思路​

这道题的关键在于如何判断两个区间是否重叠，以及如何合并。

方法：排序 + 一次遍历​

首先按区间的左端点排序。排序后，可以合并的区间一定是连续的。

遍历排序后的区间列表：

  • 如果当前区间的左端点 <= 结果列表中最后一个区间的右端点，说明重叠，合并
  • 否则，将当前区间加入结果列表

图解示例​

以 intervals = [[1,3],[2,6],[8,10],[15,18]] 为例：

第一步：排序（已排序）
intervals = [[1,3], [2,6], [8,10], [15,18]]

第二步：遍历合并
result = []

处理 [1,3]：
  result 为空，直接加入
  result = [[1,3]]

处理 [2,6]：
  检查是否与 result 最后一个区间 [1,3] 重叠
  2 <= 3? 是，重叠！
  合并：右端点取 max(3, 6) = 6
  result = [[1,6]]

处理 [8,10]：
  检查是否与 result 最后一个区间 [1,6] 重叠
  8 <= 6? 否，不重叠
  直接加入
  result = [[1,6], [8,10]]

处理 [15,18]：
  检查是否与 result 最后一个区间 [8,10] 重叠
  15 <= 10? 否，不重叠
  直接加入
  result = [[1,6], [8,10], [15,18]]

最终结果：[[1,6], [8,10], [15,18]]

Java 代码实现​

class Solution {
    public int[][] merge(int[][] intervals) {
        // 边界条件
        if (intervals.length == 0) {
            return new int[0][0];
        }
        
        // 按左端点排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // 结果列表
        List<int[]> result = new ArrayList<>();
        
        // 加入第一个区间
        result.add(intervals[0]);
        
        for (int i = 1; i < intervals.length; i++) {
            // 获取结果列表中最后一个区间
            int[] last = result.get(result.size() - 1);
            
            // 判断是否重叠
            if (intervals[i][0] <= last[1]) {
                // 重叠，合并（更新右端点）
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                // 不重叠，加入新区间
                result.add(intervals[i]);
            }
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

复杂度分析​

时间复杂度：O(n log n)，主要是排序的时间。

空间复杂度：O(log n)，排序需要的栈空间（不考虑输出数组）。

重叠判断的原理​

两个区间 [a, b] 和 [c, d] 重叠的条件是什么？

  • 如果 c <= b，说明第二个区间的起点在第一个区间内，一定重叠
  • 如果 c > b，说明两个区间不重叠

这就是为什么按左端点排序后，只需检查 intervals[i][0] <= last[1]。

189. 轮转数组 (Rotate Array)​

题目描述​

给定一个整数数组 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(n)，空间复杂度 O(n)。

方法二：三次反转（原地）​

观察规律，向右轮转 k 步，实际上是：

  1. 将后 k 个元素移到前面
  2. 将前 n-k 个元素移到后面

可以通过三次反转实现：

  1. 反转整个数组
  2. 反转前 k 个元素
  3. 反转后 n-k 个元素

图解示例​

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

原始数组：
[1, 2, 3, 4, 5, 6, 7]

第一步：反转整个数组
[7, 6, 5, 4, 3, 2, 1]

第二步：反转前 k=3 个元素
[5, 6, 7, 4, 3, 2, 1]

第三步：反转后 n-k=4 个元素
[5, 6, 7, 1, 2, 3, 4]

最终结果：[5, 6, 7, 1, 2, 3, 4]

Java 代码实现​

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        // 处理 k 大于数组长度的情况
        k = k % n;
        
        // 三次反转
        // 1. 反转整个数组
        reverse(nums, 0, n - 1);
        // 2. 反转前 k 个元素
        reverse(nums, 0, k - 1);
        // 3. 反转后 n-k 个元素
        reverse(nums, k, n - 1);
    }
    
    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

复杂度分析​

时间复杂度：O(n)，每个元素被访问两次（反转两次）。

空间复杂度：O(1)，原地操作，只使用了常数变量。

为什么三次反转有效？​

设原始数组为 A B，其中 A 是前 n-k 个元素，B 是后 k 个元素。

目标是得到 B A。

操作过程：

  1. 反转整个数组 A B → (A B)^R = B^R A^R
  2. 反转前 k 个 B^R → B
  3. 反转后 n-k 个 A^R → A
  4. 最终结果：B A

238. 除自身以外数组的乘积 (Product of Array Except Self)​

题目描述​

给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1：

输入：nums = [1,2,3,4]
输出：[24,12,8,6]
解释：
answer[0] = 2*3*4 = 24
answer[1] = 1*3*4 = 12
answer[2] = 1*2*4 = 8
answer[3] = 1*2*3 = 6

示例 2：

输入：nums = [-1,1,0,-3,3]
输出：[0,0,9,0,0]

约束条件：

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • 保证数组 nums 之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内

解题思路​

这道题要求不能用除法，那就需要找到其他方法。

方法：前缀积 + 后缀积​

对于每个位置 i，answer[i] 可以分解为：

  • prefix[i]：nums[0] 到 nums[i-1] 的乘积
  • suffix[i]：nums[i+1] 到 nums[n-1] 的乘积
  • answer[i] = prefix[i] * suffix[i]

可以用两个数组分别存储前缀积和后缀积，但更优雅的方法是利用 answer 数组本身，只用 O(1) 额外空间。

图解示例​

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

第一步：计算前缀积
answer[0] = 1（没有前缀元素，设为 1）
answer[1] = 1
answer[2] = 1 * 2 = 2
answer[3] = 1 * 2 * 3 = 6

answer = [1, 1, 2, 6]

第二步：从右往左计算后缀积，同时乘入 answer
初始化 suffix = 1

i = 3:
  answer[3] = answer[3] * suffix = 6 * 1 = 6
  suffix = suffix * nums[3] = 1 * 4 = 4
  
i = 2:
  answer[2] = answer[2] * suffix = 2 * 4 = 8
  suffix = suffix * nums[2] = 4 * 3 = 12
  
i = 1:
  answer[1] = answer[1] * suffix = 1 * 12 = 12
  suffix = suffix * nums[1] = 12 * 2 = 24
  
i = 0:
  answer[0] = answer[0] * suffix = 1 * 24 = 24
  suffix = suffix * nums[0] = 24 * 1 = 24

最终结果：[24, 12, 8, 6]

Java 代码实现​

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        
        // 第一步：answer 存储前缀积
        answer[0] = 1;  // 第一个元素没有前缀
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }
        
        // 第二步：从右往左乘以后缀积
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * suffix;
            suffix = suffix * nums[i];
        }
        
        return answer;
    }
}

复杂度分析​

时间复杂度：O(n)，两次遍历数组。

空间复杂度：O(1)，不考虑输出数组，只使用了一个变量 suffix。

为什么初始化 answer[0] = 1？​

answer[i] 存储的是 nums[0] 到 nums[i-1] 的乘积。对于 i = 0，没有前缀元素，乘积应该为 1（乘法的单位元）。

41. 缺失的第一个正数 (First Missing Positive)​

题目描述​

给你一个未排序的整数数组 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

解题思路​

这道题的难点在于 O(n) 时间和 O(1) 空间。

方法：原地哈希​

核心思想：让数值 k 出现在下标 k-1 的位置。

  1. 遍历数组，对于每个元素 nums[i]，如果它是正整数且在 [1, n] 范围内，尝试将它放到正确的位置 nums[i]-1
  2. 交换后继续处理当前位置的新元素，直到无法交换
  3. 最后遍历数组，找到第一个 nums[i] != i+1 的位置，返回 i+1

图解示例​

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

原始数组：[3, 4, -1, 1]
目标：让数字 k 出现在位置 k-1

i = 0, nums[0] = 3:
  3 应该在位置 2
  交换 nums[0] 和 nums[2]: [-1, 4, 3, 1]
  nums[0] = -1，不在 [1,4] 范围，停止
  
i = 1, nums[1] = 4:
  4 应该在位置 3
  交换 nums[1] 和 nums[3]: [-1, 1, 3, 4]
  nums[1] = 1，应该在位置 0
  交换 nums[1] 和 nums[0]: [1, -1, 3, 4]
  nums[1] = -1，不在 [1,4] 范围，停止
  
i = 2, nums[2] = 3:
  3 应该在位置 2，已经在正确位置
  
i = 3, nums[3] = 4:
  4 应该在位置 3，已经在正确位置

最终数组：[1, -1, 3, 4]

查找缺失的正整数：
  nums[0] = 1 = 0+1 ✓
  nums[1] = -1 ≠ 1+1 = 2 ✗
  
找到！缺失的最小正整数是 2

Java 代码实现​

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // 原地哈希：将数字 k 放到位置 k-1
        for (int i = 0; i < n; i++) {
            // 当 nums[i] 是正整数且在 [1,n] 范围内，且不在正确位置时
            // 注意：nums[i] != nums[nums[i] - 1] 防止无限循环
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                // 交换到正确位置
                int correctIndex = nums[i] - 1;
                int temp = nums[i];
                nums[i] = nums[correctIndex];
                nums[correctIndex] = temp;
            }
        }
        
        // 查找第一个不在正确位置的数字
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        // 如果都在正确位置，缺失的是 n+1
        return n + 1;
    }
}

复杂度分析​

时间复杂度：O(n)，虽然有两层循环，但每个元素最多被交换一次。

空间复杂度：O(1)，原地操作。

为什么答案最多是 n+1？​

如果数组包含 1 到 n 的所有正整数，答案就是 n+1。否则答案一定在 [1, n] 范围内。

相关题目​