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

第二天任务

977.有序数组的平方

题目建议： 本题关键在于理解双指针思想
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
思路：找到第一个非负数，然后双指针往两边从小到大排序查找。
自己的解法虽然用到了双指针，但是太啰嗦，得用Carl的思路再实现一下，从index=0和index=length-1的位置从大往小排序查找。

/**
     * 双指针解法
     * 3种情况：
     * 1. 全是负数，平方后倒序排；例如：[-5,-3,-2,-1], [-1]
     * 2. 全是正数，平方后正序排
     * 3. 从负数到正数
     *
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {

        final int length = nums.length;
        int[] newNums = new int[length];

        // 第一个是否正数
        boolean firstPositive = nums[0] >= 0;
        // 全是负数，倒序即可
        if (!firstPositive && nums[length - 1] < 0) {
            for (int i = 0, j = length - 1; i < length && j >= 0; ) {
                newNums[i] = nums[j] * nums[j];
                i++;
                j--;
            }
            return newNums;
        }
        int right = -1;
        for (int i = 0; i < length; i++) {
            final int num = nums[i];
            if (right < 0 && num >= 0) {
                right = i;
            }
            newNums[i] = nums[i] * nums[i];
        }
        // 全是正数，正序即可
        if (firstPositive) {
            return newNums;
        }
        // 从负数，到正数
        int left = right - 1;
        int[] newNums2 = new int[length];
        int newIndex = 0;
        do {
            final int leftVal = newNums[left];
            final int rightVal = newNums[right];
            if (leftVal <= rightVal) {
                newNums2[newIndex] = leftVal;
                left--;
            } else {
                newNums2[newIndex] = rightVal;
                right++;
            }
            newIndex++;
        } while (left >= 0 && right <= (length - 1));
        // 放入剩余的数
        while (left >= 0) {
            newNums2[newIndex++] = newNums[left--];
        }
        while (right <= (length - 1)) {
            newNums2[newIndex++] = newNums[right++];
        }
        return newNums2;
    }

209.长度最小的子数组

题目建议： 本题关键在于理解滑动窗口，这个滑动窗口看文字讲解 还挺难理解的，建议大家先看视频讲解。 拓展题目可以先不做。
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
思路：暴力解法超时了，滑动窗口的思路需要多练习。

/**
     * 双指针，滑动窗口
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int begin = 0;
        int minLen = Integer.MAX_VALUE;
        int sum = 0;
        // 全加起来也小于目标值
        boolean lessThanTarget = true;

        for (int end = 0; end < nums.length; end++) {
            sum += nums[end];

            // 用while不用if，因为可能出现[1,1,1,1,1,100]
            while (sum >= target) {
                lessThanTarget = false;
                minLen = Integer.min(end - begin + 1, minLen);

                sum -= nums[begin];
                begin++;
            }
        }

        return lessThanTarget ? 0 : minLen;

    }

59.螺旋矩阵II

题目建议： 本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
思路：这种题第一次见到，以为会有高深的算法，其实主要是考虑清楚逻辑，然后处理边界值的问题，根据Carl的思路写出了解法。

public int[][] generateMatrix(int n) {

        int[][] result = new int[n][n];

        // 转几圈
        int circleCount = n / 2;

        int startX = 0;
        int startY = 0;
        int count = 1;
        int offset = 1;
        int val = 1;

        while (count <= circleCount) {

            int x = startX, y = startY;
            //第1条边：从左到右
            for (; x < n - offset; x++) {
                result[y][x] = val++;
//              System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
            }

            //第2条边：从右上到右下
            for (; y < n - offset; y++) {
                result[y][x] = val++;
//              System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
            }

            //第3条边：从右下到左下
            for (; x >= offset; x--) {
                result[y][x] = val++;
//              System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
            }

            //第4条边：从左下到左上
            for (; y >= offset; y--) {
                result[y][x] = val++;
//              System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
            }

            // 圈数增加
            count++;
            startX++;
            startY++;
            offset++;

        }
        // 如果是奇数，填补中间的数
        if (n % 2 != 0) {
            result[startX][startY] = val;
        }
        return result;
    }