13 前缀和：最大子数组和 53

这道题不知道是不是从前做过，反正咱看一眼就有了思路。
这不就是找前缀和的最大差值吗？
记录前缀和的时间复杂度是O(n)
但是咋找最大的差值呢？
想不出来，直接暴力。
时间复杂度是\(O(n^{2})\)
果不其然，超时了！！！

既然如此，问题就在于如何遍历找到最大的差值？

我想。
左指针维护一个最小值，右指针不断更新元素，取最大差值更新。

嘻嘻嘻，做出来了！

点击查看代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> vec(nums.size() + 1);
        // vec记录每个数组元素的前缀和
        vec[0] = 0;
        for (int i = 0; i < nums.size(); ++i) {
            vec[i + 1] = vec[i] + nums[i];
        }
        // 找这些前缀和的最大差值
        int ans = INT_MIN;
        int left = 0;
        for (int right = 1; right < vec.size(); ++right) {
            ans = max(vec[right] - vec[left], ans);
            if (vec[right] < vec[left])
                left = right;
        }
        return ans;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

继续优化的话，就是空间复杂度是O(1)，因为这个前缀和可以一边遍历一边算。

然后看题解说是还可以动态规划做，嗯，目前没学过动态规划，暂时也不想了解，那就下一题吧。

56 合并区间 这道题我之前就做过了，现在不知道忘了没，再尝试一下吧。

也是不太顺利地写出来了。

点击查看代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        ranges::sort(intervals); //排序O(nlogn)
        vector<vector<int>> result;
        int left = 0, right = 1;
        for (auto& interval: intervals) {
            if (result.empty())
                result.push_back(interval);

            if (interval[left] <= result.back()[right])         {
                result.back()[right] = max(interval[right], result.back()[right]);
            }
            else
                result.push_back(interval);
        }
        return result;   
    }
};

咱就是说，最开始碰到这道题的时候，难为了我好长时间。
即便是现在我也不能把它立即写出来。

而且让我疑惑的点还是，
vec.begin()它是类似于一个指针int* p???
vec.back()和begin()类似吗？

Ok,AI给了我答案。
begin()确是指针。
但back()确是最后一个元素的引用。
记清楚了，哥们。

虽然你没看过SGI源代码，但是也要多加利用STL这个利器。

189 轮换数组

至少想出3种方法，天哪，杀了我吧。

看了一会儿，大概明白是咋回事了。
就让前k个元素和后k个元素交换一下，剩下两坨：中间一坨没交换的，最后面一坨交换过来的前k个元素。

好了，想不出来，脑子崩掉了，再见。
哦，不，是明天见！

2025-06-03 08:25:12 星期二

三种方法，为啥我一种也想不出来。
我现在已经发现关系是这样的了，nums[i+k] = nums[i];
OK，最简单的方式是借助空间。

点击查看代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> vec(nums);
        for (int i = 0; i < nums.size(); ++i)
            vec[(i + k) % nums.size()] = nums[i];
        for (int i = 0; i < nums.size(); ++i)
            nums[i] = vec[i];
    }
};

时间复杂度：O(n) 空间复杂度：O(n)

还可以进一步优化吗？
时间上，双重循环变成1重循环可以吗？
看样子不行。
那空间上，原地旋转可以吗？
按理说应该是可以的，但是我一时间想不出来，看题解吧。

点击查看代码

class Solution {
public:
    void reverse(vector<int>& nums, int begin, int end) {
        //翻转固定区间内的元素
        while (begin < end) {
            swap(nums[begin], nums[end-1]);
            ++begin,--end;
        }
    }
    void rotate(vector<int>& nums, int k) {
       k = k % nums.size();
       reverse(nums, 0, nums.size()); //整体翻转一遍
       reverse(nums, 0, k);
       reverse(nums, k, nums.size());
    }
};

参考答案如上。
这个翻转元素我确实没有想到，更别说我没观察到这一点，当k=nums.size()时，数组相当于没变；而当k>nums.size()时，数组每个元素相当于移动了k%nums.size()的步数。

OK，下一题 238 除自身以外数组的乘积

点击查看代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
    //借助辅助空间
    //一个数组记录前缀乘积
    //一个数组记录后缀乘积
    vector<int> prefix(nums.size() + 1);
    vector<int> suffix(nums.size() + 1);
    prefix[0] = 1;
    for (int i = 0; i < nums.size(); ++i) {
        prefix[i+1] = prefix[i]*nums[i];
    }
    suffix[nums.size()] = 1;
    for (int i = nums.size()-1; i >= 0; --i) {
        suffix[i] = suffix[i+1]*nums[i];
    }
    vector<int> result;
    for (int i = 0; i < nums.size(); ++i) {
        //nums[i]的前缀乘积*nums[i]的后缀乘积
        result.push_back(prefix[i]*suffix[i+1]);
    }
    return result;
    }
};

也是有惊无险地做出来了。
时间复杂度：O(n)
空间复杂度：O(n)

空间复杂度可以进一步优化成O(1)，就是一边遍历一边记录该元素的前缀和和后缀和，我知道思想是这样，但是具体实现不会。

点击查看代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
    //看一下空间复杂度为O(1)的做法
    int n = nums.size();
    vector<int> suf(n);
    suf[n-1] = 1;
    for (int i = n-2; i >= 0; --i)
        suf[i] = suf[i+1]*nums[i+1];
    int pre = 1;
    for (int i = 0; i < n; ++i) {
        suf[i] *= pre;
        pre *= nums[i];
    }
    return suf;
    }
};

代码不是很难理解，就是想不到。

OK，下一道题

41 缺失的第1个正数

这道题的难度竟然是困难？？？

我竟然做出来了。

点击查看代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //不能排序，时间复杂度是O(nlogn)
        //遍历元素，插入哈希表
        unordered_set<int> st;
        int ans = 1;
        for (auto& val: nums) {
            st.insert(val);
        }
        while (st.contains(ans)) {
            ++ans;
        }
        return ans;
    }
};

不敢相信这么简单的吗？
时间复杂度：O(n)
空间复杂度：O(n)

好吧，原来题目上要求了空间复杂度为O(1)，那连哈希表都不能用了。
直接看题解吧。看完这篇题解我们今天就到这里吧。

已经看完了，灵神的思路超级棒！