代码随想录算法训练营第二天| 977 有序数组的平方 209 长度最小的子数组 59 螺旋矩阵 ||

目录

977 有序数组的平方

209 长度最小的子数组

59 螺旋矩阵 ||

977 有序数组的平方

?先使数组存储递减序列，最后反转数组使其非递减

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int l = 0,r = nums.size() - 1;
        vector<int>res(nums.size());
        int i = 0;
        for(int i = 0;i < nums.size();i++){
            if(abs(nums[r]) > abs(nums[l])){
                res[i] = nums[r] * nums[r--]; 
            }else{
                res[i] = nums[l] * nums[l++];
            }
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

时间复杂度O(n)

空间复杂度O(n)

209 长度最小的子数组

?快慢指针

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = nums.size();
        int sum = 0;
        for(int i = 0;i < nums.size();i++)sum += nums[i];
        if(sum < target)return 0;
        sum = 0;
        for(int r = 0,l = 0;r < nums.size();r++){
            sum += nums[r];
            while(sum >= target){
                res = min(res,r - l + 1);
                sum -= nums[l++];
            }
        }
        return res;
    }
};

时间复杂度O(n)

空间复杂度O(1)

59 螺旋矩阵 ||

?模拟即可

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>>res(n,vector<int>(n));
        int w = 0,s = n - 1,a = 0,d = n - 1,cnt = 1;
        while(cnt <= n * n){
            for(int i = a;i <= d;i++)res[w][i] = cnt++;
            w++;
            for(int i = w;i <= s;i++)res[i][s] = cnt++;
            d--;
            for(int i = d;i >= a;i--)res[s][i] = cnt++;
            s--;
            for(int i = s;i >= w;i--)res[i][a] = cnt++;
            a++;
        }
        return res;
    }
};

空间复杂度O(1)//返回了res，不计算在空间复杂度内

时间复杂度O(n^2)?