在之前刷力扣的过程中，我每刷道题都是先看题解然后再去边写边看，很多内容根本没消化，在进度上欺骗自己，感觉之前刷的都忘了，能力没有什么提升，现在还是一道都不会做。所以这次报了卡哥的算法训练营，希望能够按计划地有效刷题。本次刷题，我用的是 Java 语言解题，有余力的话也可能会加上 C++ 的题解。以下是算法训练营第二天的刷题记录和思考笔记。

一、977 有序数组的平方

题目

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

1
2
3
4

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

解题思路

老规矩，用暴力排序开始美好的一天。先每个数平方，再调用 ArrayList.sort() 快速排序。

1
2
3
4
5
6
7
8
9

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

数组其实是有序的， 显然，如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法了，i 指向起始位置，j 指向终止位置。

定义一个新数组 result，和 nums 数组一样的大小，让 pos 指向 result 数组终止位置。如果 nums[i] * nums[i] < nums[j] * nums[j] 那么 result[k--] = nums[j] * nums[j]; 。如果 nums[i] * nums[i] >= nums[j] * nums[j] 那么 result[k--] = nums[i] * nums[i]; 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int result[] = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {    // 注意这里要i <= j，因为最后要处理两个元素
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                result[pos] = nums[i] * nums[i];
                i++;
            } else {
                result[pos] = nums[j] * nums[j];
                j--;
            }
            pos--;
        }
        return result;
    }
}

二、209 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。

1
2
3

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解题思路

暴力法超出时间限制。需要使用数组操作中另一个重要的方法：滑动窗口。所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。窗口就是满足其和 ≥ s 的长度最小的连续子数组。如果当前窗口的值大于 s 了，窗口就要向前移动了（也就是该缩小了）。窗口的结束位置就是遍历数组的指针，也就是 for 循环里的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;    // 取最大值
        for (int right = 0; right < nums.length ; right++){
            sum += nums[right];
            while (sum >= s){
                result = Math.min(result, right-left+1);    // 取二者间最小值
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;    // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    }
}

三、59 螺旋矩阵 II

题目

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

1
2

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

解题思路

这道题目可以说在面试中出现频率较高的题目，本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。模拟顺时针画矩阵的过程：填充上行从左到右 -> 填充右列从上到下 -> 填充下行从右到左 -> 填充左列从下到上，由外向内一圈一圈这么画下去。

同二分法相似，求解本题依然是要坚持循环不变量原则，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

生成一个 n×n 空矩阵 result，随后模拟整个向内环绕的填入过程。定义每次循环的开始点 (start, start)，和控制循环次数 loop，定义填充数字 count。当 loop++ < n / 2 时，始终按照从左到右、从上到下、从右到左、从下到上填入顺序循环，每次填入后执行 num += 1，得到下一个需要填入的数字。然后更新边界，例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public int[][] generateMatrix(int n) {
        int loop = 0;
        int[][] result = new int[n][n];
        int start = 0;
        int count = 1;
        int i, j;
        while (loop++ < n / 2) {
            for (j = start; j < n - loop; j++) {
                result[start][j] = count;
                count++;
            }

            for (i = start; i < n - loop; i++) {
                result[i][j] = count;
                count++;
            }

            for (; j >= loop; j--) {
                result[i][j] = count;
                count++;
            }

            for (; i >= loop; i--) {
                result[i][j] = count;
                count++;
            }
            start ++;
        }

        if (n % 2 == 1) {      	// 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
            result[start][start] = count;
        }
        return result;
    }
}

总结：对于正方形的二维教组只需要考虑转多少圈以及最后中间是否剩一个值， 如果剩一个一个值需要再转完圈后再单独加中间的值。另外转圈过程要保证坚持左闭右开或者左开方闭。对于矩形二维数组变成一维数组的情况，需要在较完图后单独考志最内圈剩的一行或者一列。

四、数组的经典题目总结

在面试中，数组是必考的基础数据结构。其实数组的题目在思想上一般比较简单的，但是如果想高效，并不容易。之前一共做了五道经典数组题目，每一道题目都代表一个类型，一种思想，从二分法到双指针法，从滑动窗口到螺旋矩阵。

根据题目的数据量范围选择合适的算法，比如数据量是 10^5，那就只能使用 O(nlogn) 复杂度以下的算法了，使用 O(n^2) 是会超时的，而如果数据量只有 100 或者 1000，则可以果断的采用暴力方法（一般是 O(n^2)）进行求解。

二分法的最大优势是在于其时间复杂度是 O(logn)，因此看到有序数组都要第一时间反问自己是否可以使用二分法。

双指针法移除元素和二分法这两题之间是有点类似的，他们都是在不断缩小 left 和 right 之间的距离，每次需要判断的都是 left 和 right 之间的数是否满足特定条件。

滑动窗口的本质是满足了单调性，即左右指针只会往一个方向走且不会回头。滑动窗口收缩的本质就是去掉不再需要的元素，也就是我们可以先固定移动右指针，通过判断条件是否可以收缩左指针算范围。

关于螺旋矩阵，可以同时看一下力扣上最高评的题解，代码更简洁。

LeetCode

Bezhuang