5. 普通数组

约 1869 字大约 6 分钟

LeetcodePythonC++

2025-10-19

5. 普通数组

5.1 最大子数组和

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
提示
思路：前缀和+贪心。看到连续子数组，就要想到可以转化为两个前缀和之差，需要子数组和最大，那么就是前缀和差值最大，也就是被减数最大，减数最小，类似买股票，低买高卖。只需要维护前缀最小值和最大值（直接计算最大答案）。
Python
```
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
    min_pre_sum = pre_sum = 0
    res = -inf
    for num in nums:
        pre_sum += num
        res = max(res, pre_sum - min_pre_sum)
        min_pre_sum = min(min_pre_sum, pre_sum)
    return res
```
C++
```
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre_sum = 0, min_pre_sum = 0;
        int res = INT_MIN;
        for (int x : nums) {
            pre_sum += x;
            res = max(res, pre_sum - min_pre_sum);
            min_pre_sum = min(min_pre_sum, pre_sum);
        }
        return res;
    }
};
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ 。仅用到若干额外变量。

5.2 合并区间

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] 可被视为重叠区间。
提示
思路：排序。按照左端点排序，如果左边区间的右端点大于右边区间的左端点，那么就可以合并，右端点选最大的，否则寻找下一个合并区间。
Python
```
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort(key=lambda x: x[0])
    res = []
    for p in intervals:
        if res and res[-1][1] >= p[0]:
            res[-1][1] = max(p[1], res[-1][1])
        else:
            res.append(p)
    return res
```
C++
```
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        ranges::sort(intervals);
        for (auto p : intervals) {
            if (!res.empty() && res.back()[1] >= p[0]) {
                res.back()[1] = max(res.back()[1], p[1]);
            }
            else {
                res.emplace_back(p);
            }
        }
        return res;
    }
};
```
重要
emplace_back() 是 push_back() 的一种更高效写法。
它会在容器末尾原地构造一个新元素，而不是先创建一个临时变量再拷贝进去。
时间复杂度： $O(nlogn)$ ，其中 n 是 intervals 的长度。瓶颈在排序上。
空间复杂度： $O(1)$ 。排序的栈开销和返回值不计入。

5.3 轮转数组

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]

提示

思路：前缀积和后缀积。

Python

class Solution:
def rotate(self, nums: List[int], k: int) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    def reverse(i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
    n = len(nums)
    k = k % n
    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)

C++

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        ranges::reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

时间复杂度： $O(n)$ ，其中 n 是 nums 的长度。

空间复杂度： $O(1)$ 。

5.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]

提示

思路：前缀积和后缀积。分别算出前缀积和后缀积，那么前缀积乘后缀积就是除自身以外数组的乘积。

Python

class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    pre = [1] * n
    for i in range(1, n):
        pre[i] = pre[i - 1] * nums[i - 1]
    suf = [1] * n
    for i in range(n - 2, -1, -1):
        suf[i] = suf[i + 1] * nums[i + 1]
    return [p * s for p, s in zip(pre, suf)]

C++

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n, 1);
        vector<int> suf(n, 1);
        vector<int> res(n);
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < n; i++) {
            res[i] = pre[i] * suf[i];
        }
        return res;
    }
};

时间复杂度： $O(n)$ ，其中 n 是 nums 的长度。

空间复杂度： $O(n)$ 。

5.5 缺失的第一个正数

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 没有出现。

提示

思路：灵神的排座位思路太神了。

Python

class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
        
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

C++

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && 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;
            }
        }
        return n + 1;
    }
};

时间复杂度： $O(n)$ ，其中 n 是 nums 的长度。虽然我们写了个二重循环，但每次交换都会把一个学生换到正确的座位上，所以总交换次数至多为 n，所以内层循环的总循环次数是 $O(n)$ 的，所以时间复杂度是 $O(n)$ 。

空间复杂度： $O(1)$ 。