hot100普通数组题解

发表于 2025/01/15 更新于 2025/01/15

作者 匆匆那年 26 分钟阅读

53. 最大子数组和

问题描述

给你一个整数数组 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：动态规划（Kadane 算法，线性时间复杂度 $O(n)$）

定义状态：
- dp[i] 表示以 nums[i] 为结尾的子数组的最大和。
- 状态转移方程：
  $dp[i] = \max(nums[i], dp[i-1] + nums[i])$
  即：
  - 如果 dp[i-1] + nums[i] 更大，则继续扩展子数组。
  - 否则，从当前元素重新开始一个子数组。
优化空间：
- 由于每次计算 dp[i] 只依赖于 dp[i-1]，可以只用一个变量 currentSum 来代替 dp 数组，从而将空间复杂度优化到$O(1)$。
步骤：
- 初始化 currentSum 为第一个元素，maxSum 为第一个元素。
- 遍历数组，更新 currentSum 和 maxSum。

方法 2：分治法（进阶解法，复杂度 $O(n \log n)$）

递归分治：
- 将数组分为左右两部分，分别计算左半部分和右半部分的最大子数组和。
- 计算跨越中间点的最大子数组和。
- 取以上三者的最大值。
时间复杂度：
- 分治法每次分割数组需要 $O(\log n)$ 次递归，每次合并结果需要 $O(n)$，因此总体复杂度为 $O(n \log n)$。

方法 1：动态规划代码实现（推荐）

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSubArray(vector<int>& nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];

    for (int i = 1; i < nums.size(); ++i) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }

    return maxSum;
}

int main() {
    vector<int> nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> nums2 = {1};
    vector<int> nums3 = {5, 4, -1, 7, 8};

    cout << "最大子数组和: " << maxSubArray(nums1) << endl; // 输出 6
    cout << "最大子数组和: " << maxSubArray(nums2) << endl; // 输出 1
    cout << "最大子数组和: " << maxSubArray(nums3) << endl; // 输出 23

    return 0;
}

方法 2：分治法代码实现

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int crossSum(vector<int>& nums, int left, int mid, int right) {
    int leftSum = INT_MIN, rightSum = INT_MIN;
    int sum = 0;

    // 计算左侧最大和
    for (int i = mid; i >= left; --i) {
        sum += nums[i];
        leftSum = max(leftSum, sum);
    }

    // 计算右侧最大和
    sum = 0;
    for (int i = mid + 1; i <= right; ++i) {
        sum += nums[i];
        rightSum = max(rightSum, sum);
    }

    return leftSum + rightSum;
}

int divideAndConquer(vector<int>& nums, int left, int right) {
    if (left == right) return nums[left];

    int mid = left + (right - left) / 2;

    int leftMax = divideAndConquer(nums, left, mid);
    int rightMax = divideAndConquer(nums, mid + 1, right);
    int crossMax = crossSum(nums, left, mid, right);

    return max({leftMax, rightMax, crossMax});
}

int maxSubArray(vector<int>& nums) {
    return divideAndConquer(nums, 0, nums.size() - 1);
}

int main() {
    vector<int> nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> nums2 = {1};
    vector<int> nums3 = {5, 4, -1, 7, 8};

    cout << "最大子数组和: " << maxSubArray(nums1) << endl; // 输出 6
    cout << "最大子数组和: " << maxSubArray(nums2) << endl; // 输出 1
    cout << "最大子数组和: " << maxSubArray(nums3) << endl; // 输出 23

    return 0;
}

复杂度分析

动态规划:
- 时间复杂度: $O(n)$，只需遍历一次数组。
- 空间复杂度: $O(1)$，只使用了常量空间。
分治法:
- 时间复杂度: $O(n \log n)$。
- 空间复杂度: $O(\log n)$，递归栈的深度。

示例输出

最大子数组和: 6
最大子数组和: 1
最大子数组和: 23

总结

对于该问题，动态规划方法是最优解，具有更低的时间和空间复杂度，适合大规模输入。分治法虽然进阶，但实际应用中效率略逊。

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

提示：

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

题解

解题思路

排序：
- 首先按区间的起始位置从小到大对所有区间进行排序。
- 排序的目的是确保我们可以按顺序处理区间，从而判断是否存在重叠。
合并区间：
- 使用一个结果数组 merged，初始化为空。
- 遍历排序后的区间：
  - 如果结果数组为空，或者当前区间的起始值大于结果数组最后一个区间的结束值，说明没有重叠，将当前区间加入结果数组。
  - 否则，说明当前区间与结果数组最后一个区间有重叠，更新最后一个区间的结束值为两者结束值的最大值。
输出结果：
- 返回合并后的 merged 数组。

C++代码实现

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};

    // 按区间的起始位置排序
    sort(intervals.begin(), intervals.end());

    vector<vector<int>> merged;

    for (const auto& interval : intervals) {
        // 如果结果数组为空，或当前区间不与结果数组的最后一个区间重叠
        if (merged.empty() || merged.back()[1] < interval[0]) {
            merged.push_back(interval);
        } else {
            // 存在重叠，更新最后一个区间的结束值
            merged.back()[1] = max(merged.back()[1], interval[1]);
        }
    }

    return merged;
}

int main() {
    vector<vector<int>> intervals1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    vector<vector<int>> intervals2 = {{1, 4}, {4, 5}};

    auto result1 = merge(intervals1);
    auto result2 = merge(intervals2);

    cout << "合并后的区间: ";
    for (const auto& interval : result1) {
        cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    cout << endl;

    cout << "合并后的区间: ";
    for (const auto& interval : result2) {
        cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    cout << endl;

    return 0;
}

复杂度分析

时间复杂度:
- 排序的时间复杂度为 $O(n \log n)$，其中 $n$ 是区间的数量。
- 遍历区间合并的时间复杂度为 $O(n)$。
- 总时间复杂度为 $O(n \log n)$。
空间复杂度:
- 排序所需的空间复杂度取决于排序算法（一般为 $O(\log n)$）。
- 结果数组的空间复杂度为 $O(n)$。
- 总空间复杂度为 $O(n)$。

示例输出

合并后的区间: [1,6] [8,10] [15,18] 
合并后的区间: [1,5] 

总结

通过先排序后合并的方法，可以高效地解决区间合并问题。
这种方法非常通用，适用于处理重叠区间的多种变体。

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) 的原地算法解决这个问题吗？

解题思路

解决数组轮转问题，可以使用以下三种主要方法：

方法 1：使用额外数组（简单直观）

创建一个新数组，将原数组的元素按轮转后的顺序放入新数组。
将新数组的值复制回原数组。
时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

方法 2：环状替换（原地算法）

通过数学公式计算元素在轮转后的目标位置。
使用一个计数器来追踪已移动的元素，直到所有元素都移动到正确位置。
时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

方法 3：三步反转法（原地算法，推荐）

先将整个数组反转。
反转前 $k \mod n$ 个元素。
反转剩余的元素。
时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

C++代码实现

方法 1：使用额外数组

  
#include <iostream>
#include <vector>
using namespace std;

void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k = k % n; // 防止 k 超过数组长度
    vector<int> temp(n);
    for (int i = 0; i < n; ++i) {
        temp[(i + k) % n] = nums[i];
    }
    nums = temp;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    rotate(nums, 3);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

方法 2：环状替换

  
#include <iostream>
#include <vector>
using namespace std;

void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k = k % n; // 防止 k 超过数组长度
    int count = 0; // 记录已处理的元素数量

    for (int start = 0; count < n; ++start) {
        int current = start;
        int prev = nums[start];
        do {
            int next = (current + k) % n;
            swap(nums[next], prev);
            current = next;
            count++;
        } while (start != current);
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    rotate(nums, 3);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

方法 3：三步反转法

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void reverse(vector<int>& nums, int start, int end) {
    while (start < end) {
        swap(nums[start], nums[end]);
        start++;
        end--;
    }
}

void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k = k % n; // 防止 k 超过数组长度
    reverse(nums, 0, n - 1);     // 反转整个数组
    reverse(nums, 0, k - 1);     // 反转前 k 个元素
    reverse(nums, k, n - 1);     // 反转后 n-k 个元素
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    rotate(nums, 3);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

复杂度分析

方法 1：使用额外数组

时间复杂度: $O(n)$
空间复杂度: $O(n)$

方法 2：环状替换

时间复杂度: $O(n)$
空间复杂度: $O(1)$

方法 3：三步反转法

时间复杂度: $O(n)$
空间复杂度: $O(1)$

示例输出

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

5 6 7 1 2 3 4

对于输入 nums = [-1,-100,3,99], k = 2，输出为：

3 99 -1 -100

总结

推荐方法：三步反转法，由于它是原地算法且实现简单高效。
环状替换 适合追求精确理解数组轮转过程时使用。
额外数组 方法适合快速实现，但空间复杂度较高。

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
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

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

题解

解题思路

我们需要计算每个元素的结果数组 $\text{answer}[i]$，其值等于 nums 中所有元素的乘积，除了 nums[i] 自己。为了实现 $O(n)$ 时间复杂度且不使用除法，可以通过以下方法解决：

方法：前缀积与后缀积

前缀积:
- 定义 prefix[i] 为数组 nums 在索引 $i$ 前的所有元素的乘积，即 prefix[i] = nums[0] * nums[1] * ... * nums[i-1]。
后缀积:
- 定义 suffix[i] 为数组 nums 在索引 $i$ 后的所有元素的乘积，即 suffix[i] = nums[i+1] * nums[i+2] * ... * nums[n-1]。
合并计算:
- 我们可以通过前缀积和后缀积直接计算结果： $\text{answer}[i] = \text{prefix}[i] \times \text{suffix}[i]$
优化空间:
- 我们可以在一次遍历中计算前缀积，同时用一个变量存储后缀积，避免使用额外数组存储 prefix 和 suffix。

C++代码实现

  
#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);

    // 计算前缀积
    int prefix = 1;
    for (int i = 0; i < n; ++i) {
        answer[i] = prefix;
        prefix *= nums[i];
    }

    // 计算后缀积并更新答案
    int suffix = 1;
    for (int i = n - 1; i >= 0; --i) {
        answer[i] *= suffix;
        suffix *= nums[i];
    }

    return answer;
}

int main() {
    vector<int> nums1 = {1, 2, 3, 4};
    vector<int> nums2 = {-1, 1, 0, -3, 3};

    auto result1 = productExceptSelf(nums1);
    auto result2 = productExceptSelf(nums2);

    cout << "结果1: ";
    for (int num : result1) {
        cout << num << " ";
    }
    cout << endl;

    cout << "结果2: ";
    for (int num : result2) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

复杂度分析

时间复杂度:
- 前缀积和后缀积各需要一次遍历，时间复杂度为 $O(n)$。
空间复杂度:
- 输出数组 answer 不计入空间复杂度。
- 使用了常量级变量 prefix 和 suffix，因此空间复杂度为 $O(1)$。

示例输出

结果1: 24 12 8 6
结果2: 0 0 9 0 0

总结

关键技巧:
- 使用前缀积和后缀积，可以在不使用除法的情况下高效地计算结果。
- 空间优化的思想，通过临时变量替代额外数组，是处理类似问题的常用手段。
推荐方法:
- 该解法是空间和时间效率的最优解，适合大规模数据输入。

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$

题解

解题思路

为了在 $O(n)$ 的时间复杂度和 $O(1)$ 的空间复杂度下解决这个问题，我们可以利用 原地哈希 的思想，通过将数组中的数字放置到它们的正确位置来寻找缺失的最小正整数。

算法步骤

调整数组位置:
- 遍历数组，对于每个元素 nums[i]，如果它在范围 [1, n]（数组长度为 $n$）且 nums[i] != nums[nums[i] - 1]，就将其交换到正确位置 nums[i] - 1。
- 通过不断交换，使数组中的数字尽可能排列到它们“应有的位置”。
查找缺失的正数:
- 再次遍历数组，找到第一个位置 $i$ 满足 nums[i] != i + 1，则缺失的正整数为 $i + 1$。
- 如果数组中所有位置都正确，则返回 $n + 1$。
关键点:
- 只对数组元素进行交换操作，不使用额外空间。
- 时间复杂度为 $O(n)$，因为每个数字最多只被交换一次。

C++代码实现

  
#include <iostream>
#include <vector>
using namespace std;

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();

    // 将数字放到正确的位置
    for (int i = 0; i < n; ++i) {
        while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }

    // 找到第一个不在正确位置的数字
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    // 如果所有位置都正确，返回 n + 1
    return n + 1;
}

int main() {
    vector<int> nums1 = {1, 2, 0};
    vector<int> nums2 = {3, 4, -1, 1};
    vector<int> nums3 = {7, 8, 9, 11, 12};

    cout << "缺失的第一个正数: " << firstMissingPositive(nums1) << endl; // 输出 3
    cout << "缺失的第一个正数: " << firstMissingPositive(nums2) << endl; // 输出 2
    cout << "缺失的第一个正数: " << firstMissingPositive(nums3) << endl; // 输出 1

    return 0;
}

复杂度分析

时间复杂度:
- 每个元素最多被交换一次，因此总时间复杂度为 $O(n)$。
空间复杂度:
- 除了输入数组外，只使用了常量级别的额外空间，空间复杂度为 $O(1)$。

示例输出

缺失的第一个正数: 3
缺失的第一个正数: 2
缺失的第一个正数: 1

总结

原地哈希 是解决数组问题的经典技巧，特别是当题目要求原地操作时。
通过调整数组位置，我们能够以线性时间和常量空间完成计算，非常高效。
此方法适用于数组元素范围较小或有限的情况，尤其适合寻找位置相关的缺失值问题。

leetcode, hot100

本文由作者按照 CC BY 4.0 进行授权

53. 最大子数组和

问题描述

题解

解题思路

方法 1：动态规划（Kadane 算法，线性时间复杂度 $O(n)$）

方法 2：分治法（进阶解法，复杂度 $O(n \log n)$）

方法 1：动态规划代码实现（推荐）

方法 2：分治法代码实现

复杂度分析

示例输出

总结

56. 合并区间

问题描述

题解

解题思路

C++代码实现

复杂度分析

示例输出

总结

189. 轮转数组

问题描述

解题思路

方法 1：使用额外数组（简单直观）

方法 2：环状替换（原地算法）

方法 3：三步反转法（原地算法，推荐）

C++代码实现

方法 1：使用额外数组

方法 2：环状替换

方法 3：三步反转法

复杂度分析

方法 1：使用额外数组

方法 2：环状替换

方法 3：三步反转法

示例输出

总结

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

问题描述

题解

解题思路

方法：前缀积与后缀积

C++代码实现

复杂度分析

示例输出

总结

41. 缺失的第一个正数

问题描述

题解

解题思路

算法步骤

C++代码实现

复杂度分析

示例输出

总结

热门标签