977. 有序数组平方

1.暴力解法（平方后进行排序即可）

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

2.双指针方法（第一种）

所有数都是非负数，那么将每个数平方后，数组仍然保持升序；所有数都是负数，那么将每个数平方后，数组会保持降序。
找到数组中负数与非负数的分界线，分界线左边单调递减，分界线右边单调递增。
两个已经有序的子数组用归并的方法进行排序。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        //neg正负分界线的位置
        int neg = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0) {
                neg = i;
            } else {
                break;
            }
        }
        int index = 0;
        //i为分界线位置
        int i = neg;
        //j为分界线右边+1位置
        int j = neg + 1;
        while (i >= 0 || j < n) {
            if (i < 0) {  //i小于0，说明数组不存在负数，j的初始值为-1+1=0
                ans[index] = nums[j] * nums[j];
                j++;
            } else if (j == n) {//j等于n，说明数组只有负数，i的初始值为n-1
                ans[index] = nums[i] * nums[i];
                i--;
            } else if (nums[i] * nums[i] < nums[j] * nums[j]) {
                //负数和非负数都有，i单调递减
                ans[index] = nums[i] * nums[i];
                i--;
            } else {
                //负数和非负数都有，j单调递增
                ans[index] = nums[j] * nums[j];
                j++;
            }
            index++;
        }
        return ans;
    }
}

3.双指针方法（第二种）

左指针 0?和右指针 n?1，比较左右指针的数，选择较大的那个逆序放入答案并移动指针

class Solution {
      public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0, j = n - 1, k = n - 1; i <= j; ) {
            if (nums[i] * nums[i] < nums[j] * nums[j]) {
                ans[k] = nums[j] * nums[j];
                j--;//j为右指针，向左走
            } else {
                ans[k] = nums[i] * nums[i];
                i++;//i为左指针，向右走
            }
            k--;//逆序放入
        }
        return ans;
    }
}

209. 长度最小子数组

滑动窗口：

本题中实现滑动窗口，主要确定如下三点：

窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？

窗口就是满足其和 ≥ s 的长度最小的连续子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

解题的关键在于窗口的起始位置如何移动，如图所示：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //滑动窗口解法
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        int left = 0;
        //类似双指针，用右指针来确定窗口的走向，比target小，sum就一直加
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            //满足条件，记录最小的长度
            while (sum >= target) {
                ans = Math.min(ans, right - left + 1);
                //减小窗口
                sum -= nums[left++];
            }
        }
        //ans为初始最大值，说明sum比target小，返回0
        if (ans == Integer.MAX_VALUE) {
            return 0;
        }
        return ans;
    }
}

59. 螺旋矩阵

模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上

这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。
这也是坚持了每条边左闭右开的原则。

class Solution {
    public int[][] generateMatrix(int n) {
       int[][] ans = new int[n][n];
        int startX = 0, loop = 0, count = 1;
        int i, j;
        while (loop++ < n / 2) {
            //上方：从左到右（左闭右开），不包含最后一个值
            for (j = startX; j < n - loop; j++) {
                ans[startX][j] = count++;
            }
            //右方：从上到下（左闭右开），不包含最后一个值
            for (i = startX; i < n - loop; i++) {
                ans[i][j] = count++;
            }
            //下方：从右到左（左闭右开），不包含最后一个值
            for (; j >= loop; j--) {
                ans[i][j] = count++;
            }
            //左方：从下到上（左闭右开），不包含最后一个值
            for (; i >= loop; i--) {
                ans[i][j] = count++;
            }
            startX++;
        }
        if (n % 2 == 1) {
            ans[startX][startX] = count;
        }
        return ans;
    }
}