我新建的个人博客，欢迎访问：hmilzy.github.io

977.有序数组的平方

题目链接: 有序数组的平方

自己最先想到的思路是先遍历数组，每个元素平方。然后再对数组进行排序。但是复杂度可能较高。

思路：对于一个有正有负的有序数组，运用双指针，从数组两端开始比较并移动，较大的平方值放入新数组的最后一个位置，依次执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] sortedSquares(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        int pos = len - 1;
        int[] result = new int[len];
        while(left <= right){
            //若左指针平方数更大，则将左边的数放入新数组，并且左指针右移
            if(nums[left] * nums[left] > nums[right] * nums[right]){
                result[pos] = nums[left] * nums[left];
                pos--;
                left++;
            }else{
                //否则右指针平方数更大，则将右边的数放入新数组，并且右指针左移
                result[pos] = nums[right] * nums[right];
                pos--;
                right--;
            }
        }
        return result;
    }
}

209.长度最小的子数组

题目链接: 长度最小的子数组

方法一：暴力解法
两个for循环，会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //这里给result赋值是为了最后的时候判断是否有改变
        int result = Integer.MAX_VALUE;

        for(int i = 0; i < nums.length; i++){
            int sum = 0;
            for(int j = i; j < nums.length; j++){
                sum += nums[j];
                if(sum >= target){
                    result = Math.min(result,j - i + 1);
                    break;
                }
            }
        }
        return (result == Integer.MAX_VALUE) ? 0 : result;
    }
}

方法二：滑动窗口：不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果

  1. 只用一个for循环，那么这个循环的索引，一定是表示滑动窗口的终止位置。
  2. 当窗口内元素和满足条件，就要缩小窗口，也就是移动窗口的起始位置
  3. 滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minSubArrayLen(int target, int[] nums) {

        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            //当子数组和大于target，需要循环移动左边窗口，看是否可以缩小
            while (sum >= target) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return (result == Integer.MAX_VALUE) ? 0 : result;
    }
}

59.螺旋矩阵II

题目链接: 螺旋矩阵II

主要是要弄清每一层循环如何变：数组元素的上下标变化有什么规律

  1. 循环次数loop = n / 2。
  2. 每一圈循环下来，起始点的横纵坐标都加 1。
  3. 每一行一列的赋值，循环次数是不同的，所以定义了一个offset，每到下一圈，offset就加2。
  4. 若数组n是奇数，则最后会剩下中心位置还未赋值，单独给他赋值即可。
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    public int[][] generateMatrix(int n) {

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

        //定义循环次数  一圈一圈循环
        int loop = n / 2;

        //定义循环起始位置
        int startX = 0;
        int startY = 0;

        //定义偏移量
        int offset = 1;

        //定义填充数字
        int count = 1;

        while(loop > 0){

            int i = startX;
            int j = startY;

            //从左往右
            for(;j < startY + n - offset;j++){
                result[i][j] = count;
                count++;
            }

            //从上到下
            for(;i < startX + n - offset;i++){
                result[i][j] = count;
                count++;
            }

            //从右到左
            for(;j > startY;j--){
                result[i][j] = count;
                count++;
            }

            //从下到上
            for(;i > startX;i--){
                result[i][j] = count;
                count++;
            }

            startX++;
            startY++;
            offset += 2;
            loop--;

        }

        int middle = n / 2;
        if(n % 2 == 1){
            result[middle][middle] = n * n;
        }

        return result;
    }
}

数组章节总结

主要方法：

1.暴力解法

2.二分法

3.双指针法（快慢指针，左右相向指针）

4.滑动窗口（类似双指针）：滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)
主要确定如下三点：

  1. 窗口内是什么？ 答：窗口内是子数组元素
  2. 如何移动窗口的起始位置？ 答：当结束位置确定，起始位置依照条件开始右移，也就是缩小窗口
  3. 如何移动窗口的结束位置？ 答：窗口的结束位置是遍历的指针，for循环的索引