Day2-数组2023.9.15

Leetcode977 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

初解

我还是不能想到暴力解法之外的，对某个问题的最优复杂度也没有概念。就算提示我是用指针，我也想不到思路。
现在我知道的指针主要有快慢指针和双向指针。
受昨天那个原地换位置的影响，我也下意识没有想到新开一个数组。

看完解答

思路很简单：开一个新的数组，依次放进最大的数。最大的数必然在两侧（绝对值最大）。每次放进一个数，左右指针移动即可。
实现也很简单我一次就过了。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len=nums.size();
        int l=0,r=len-1;
        // 最大的一定在两头。
        vector<int> res;
        res.resize(len);
        int p=len-1;
        while(p>=0&&l<=r){
            if(nums[l]*nums[l]>nums[r]*nums[r]){
                res[p--]=nums[l]*nums[l];
                l++;
            }else{
                res[p--]=nums[r]*nums[r];
                r--;
            }
        }
        return res;
    }
};

Leetcode209 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

初解

滑动窗口吧，会不了一点，暴力又是\(O(n^2)\)，看答案去

看完解答

小小的误区

哦我已经完全理解了.jpg
从原来的\(O(n^2)\)暴力解法下降复杂度，只能减少一个循环。在暴力解法中，我们的第一个循环是窗口起点，第二层循环是窗口终点，判断到和>=target就break第二层。如果要减少一个循环，我们需要确定循环变量代表什么，循环节干什么，循环节之间怎么办。
滑动窗口的思想是，把窗口终点当循环变量。据题解说这是因为如果把窗口起点当循环变量的话，想要走到终点，还是要用一个循环的。而当我们把窗口终点当作循环变量的话，可以沿用上一个循环节的起点（+1）！要不然该循环节的长度也不是最小的，我们就不用管它了！而如果你用窗口起点当循环变量，终点是有可能缩回来也有可能右移的，这样谁能写得出来呢！多么天才啊！我去！
但是我还是有一个误解。我总觉得在一个循环节内，要找到最优解，然后比较每个局部最优解。如果我这么想的话，我会让窗口起点右移直到区间之和第一次不满足要求为止，之后再计算区间长度。这样会导致一个问题：此时区间起点指针已经多右移了一下。如果我简单地让它左移一下，还要考虑全区间加起来也不满足要求的情况，左移也不满足要求啊！还可能走到-1！

没有关系，我会上奇技淫巧

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len=nums.size();
        int sum=0;
        int i=0;
        int res=999999;
        for(int j=0;j<len;++j){
            sum+=nums[j];
            // find i
            int flag=0;
            while(sum>= target&&i<=j){
                // move right
                sum-=nums[i++];
                flag=1;
            }
            if(flag){
                i--;sum+=nums[i];
                int tmplen=j-i+1;
                res=tmplen<res?tmplen:res;
            }
        }
        if(res==999999){
            return 0;
        }else{
            return res;
        }
    }
};

我这里让它判断，有右移才倒带，就可以通过了。但是面试官还是可能觉得我是傻逼。

找到全部解

我从题解那里抄来一个优雅的解法

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len=nums.size();
        int sum=0;
        int i=0;
        int res=999999;
        for(int j=0;j<len;++j){
            sum+=nums[j];
            while(sum>= target&&i<=j){
                int tmplen=j-i+1;
                res=tmplen<res?tmplen:res;
                sum-=nums[i++];
            }
        }
        if(res==999999){
            return 0;
        }else{
            return res;
        }
    }
};

它的思想略和我不同，他寻找了每一个解，在每一个解里面更新最短长度。我们可爱的计算机很擅长做重复的事情，它不会觉得麻烦！