随想录刷题第二天 | 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II

977.有序数组的平方
这题第一想法是先原地平方后再排序，但看到时间要求0（n）,这就不行了。
因为原数组是一个非递减顺序，所以可以先找到绝对值最小的值然后双指针两边扫就行了

    public int[] sortedSquares(int[] nums) {
        //寻找第一个非零数
        int flag = -1;
        for (int i=0;i<nums.length;i++){
            if (nums[i] >= 0) {
                flag = i;
                break;
            }
        }

        int[] result = new int[nums.length];

        if (flag == 0){
            //全正数
            for (int i=0;i<nums.length;i++){
                result[i] = nums[i]*nums[i];
            }
        }else if (flag == -1){
            //全负数
            int temp = 0;
            for (int i=nums.length-1;i>=0;i--){
                result[temp++] = nums[i]*nums[i];
            }
        }else {
            int left = flag-1;
            //双指针比较绝对值
            int num = 0;
            while(num < nums.length){
                if (left>=0 && flag < nums.length){
                    if (nums[left]+nums[flag] >= 0){
                        result[num] = nums[left]*nums[left];
                        left--;
                    }else {
                        result[num] = nums[flag]*nums[flag];
                        flag++;
                    }
                }else if (left < 0){
                    result[num] = nums[flag]*nums[flag];
                    flag++;
                }else {
                    result[num] = nums[left]*nums[left];
                    left--;
                }
                
                num++;
            }
        }
        return result;
    }

209.长度最小的子数组
这题以前做过，但错了八次。
这次第一时间想到的是滑动窗口，先滑右边找到符合条件的数组，再滑左边减少长度，这次比之前快了

    public int minSubArrayLen(int target, int[] nums) {
        int min = nums.length+1;
        int len = nums.length;

        int cur = nums[0];
        int left = -1; int right =0;
        while (right < len){
            //滑动右边界
            while (cur < target && right < len-1){
                right++;
                cur += nums[right];
            }
            //判断是否滑到头了
            if (cur < target){
                break;
            }

            while (cur >= target && left < right){
                min = Math.min(min,right - left);
                left++;
                cur -= nums[left];
            }
        }

        return min == nums.length+1 ? 0 : min;
    }

59.螺旋矩阵II
这题纯模拟，注意前进方向和换方向的时机就行了

    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        
        //方向定义 0向右 1向下 2向左 3向上
        int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
        int flag = 0;
        //起点
        int x = 0;int y=0;
        
        int end = n*n;
        int cur = 1;
        while (cur <= end){
            result[x][y] = cur;
            //如果按照当前方向还可以前进就前进
            int dx = dir[flag][0];
            int dy = dir[flag][1];
            if (-1<x+dx && x+dx < n 
                    && y+dy > -1 && y+dy < n 
                    && result[x+dx][y+dy] == 0){
                x += dx;
                y += dy;
            }else {
                //换方向
                flag = flag < 3 ? ++flag : 0;
                x += dir[flag][0];
                y += dir[flag][1];
            }
            cur++;
        }
        
        return result;
    }