977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵 II

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

有序数组的平方

977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵 II_算法

代码

快速排序使用库函数,时间复杂度为O（nlgn），空间复杂度为O（1）

class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i = 0;i < nums.length;i++){
            nums[i] *= nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

牺牲空间复杂度换时间
双指针法，并创建一个辅助数组存值，因为存的是平方数，所以原数组左侧可能是负数平方后可能比右侧的平方大，所以依次比较大小，大的值存入辅助数组最后一个位置，具体见代码。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] nums1 = new int[nums.length];
        int k = nums.length - 1;
        for(int i = 0,j = nums.length - 1;i <= j;){
            if(Math.pow(nums[i],2) < Math.pow(nums[j],2)){
                nums1[k--] = (int)Math.pow(nums[j],2);
                j--;
            }else{
                nums1[k--] = (int)Math.pow(nums[i],2);
                i++;
            }
        }
        return nums1;
    }
}

209.长度最小的子数组

977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵 II_Math_02

无序版滑动窗口，用两个指针就可以实现滑动窗口，具体见代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int j = 0,res = Integer.MAX_VALUE,sum = 0;
        for(int i = 0;i < nums.length;i++){
            sum += nums[i];
            while(sum >= target){
                res = Math.min(res,i - j + 1);
                sum -= nums[j++];
            }
        }
        return res == Integer.MAX_VALUE?0:res;
    }
}

977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵 II_矩阵_03

59.螺旋矩阵Ⅱ

977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵 II_leetcode_04

和我之前做过的顺时针打印矩阵思路相同，那道题的链接在这里

977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵 II_算法_05

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int a = 0,b = n - 1,c = 0,d = n - 1;
        int k = 1;
        while(true){
            for(int i = a,j = c;j <= d;j++,k++){
                res[i][j] = k;
            }
            a++;
            if(a > b) break;
            for(int i = a,j = d;i <= d;i++,k++){
                res[i][j] = k;
            }
            d--;
            if(d < c) break;
            for(int i = b,j = d;j >= c;j--,k++){
                res[i][j] = k;
            }
            b--;
            if(b < a) break;
            for(int i = b,j = c;i >= a;i--,k++){
                res[i][j] = k;
            }
            c++;
            if(c > d) break;

        }
        return res;

    }
}