997.有序数组的平方

文章：4. 有序数组的平方

题目：977. 有序数组的平方

【思路】

双指针

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[]res = new int[nums.length];
        int k =nums.length-1;
        for(int i = 0,j=nums.length-1;i <= j;){
            if(nums[i]*nums[i] > nums[j] * nums[j]){
                res[k--] = nums[i] *nums[i];
                i++; 
            }else{
                res[k--] = nums[j] * nums[j];
                j--;
            }
        }
        return res;
    }
}
  • Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func sortedSquares(nums []int) []int {
    res := make([]int,len(nums))
    left,right := 0,len(nums)-1
    k := len(nums)-1  //数组下标
    for ;left <= right;{
        if nums[left]*nums[left] > nums[right] * nums[right]{
            res[k] = nums[left]*nums[left]
            k--
            left++
        }else{
            res[k] = nums[right] * nums[right]
            k--
            right--
        }
    }
    return res
}

209.长度最小的子数组

文章：5. 长度最小的子数组

题目：209. 长度最小的子数组

【思路】

滑动窗口，本质上也是双指针

  • Java
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) {
        int sum = 0;
        int res = nums.length+1;
        int j = 0;
        int sublen = 0;
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
            while(sum >= target){
                sublen = i-j+1;
                res = sublen > res? res:sublen;
                sum -= nums[j];
                j++;
            }
        }
        return res == nums.length+1 ? 0:res;
    }
}
  • Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func minSubArrayLen(target int, nums []int) int {
    res,sum,reslen :=len(nums)+1,0,0
    for i,j := 0,0;i < len(nums);i++{
        sum += nums[i]
        for sum >= target{
            reslen = i-j+1
            if res > reslen{
                res = reslen
            }
            sum -= nums[j]
            j++
        }
    }
    if res == len(nums)+1{
        return 0
    }
    return res
}

59.螺旋数组II

文章：6. 螺旋矩阵II

题目：59. 螺旋矩阵 II

【思路】

下标转圈圈

  • Java
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
class Solution {
    public int[][] generateMatrix(int n) {
       int[][]res = new int[n][n];
       int startx = 0,starty = 0;
       int count =1,offset =1;
       int mid = n/2,loop=n/2;
       int i=0,j=0;
       while (loop>0){
           i = startx;
           j = starty;
           for(j = starty;j< n-offset;j++){
               res[i][j] = count++;
           }
           for(i = startx;i< n-offset;i++){
               res[i][j] = count++;
           }
           for(;j>startx;j--){
               res[i][j] = count++;
           }
           for(;i >starty;i--){
               res[i][j] = count++;
           }
           startx++;
           starty++;
           offset++;
           loop--;
       }

       if(n%2 ==1 ){
           res[mid][mid] = count;
       }
       return res;
    }
}
  • Go
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
func generateMatrix(n int) [][]int {
	res := make([][]int,n)
    for i:=0;i<len(res);i++{
        res[i] = make([]int,n)
    }
    count,startx , starty := 1,0,0
    loop,mid := n/2,n/2
    offset :=1//默认为1，数组起始下标为0
    i,j :=0,0
    for loop>0{
        i,j = startx,starty
        for j=starty;j<n-offset;j++{
            res[i][j]= count
            count++
        }
        for i = startx;i<n-offset;i++{
            res[i][j]=count
            count++
        }
        //y-- x不变
        for ;j > starty;j--{
            res[i][j] = count
            count++
        }
        for ;i > startx;i--{
            res[i][j] = count
            count++
        }
        startx++
        starty++
        offset++
        loop--
    }
    //中间
    if n%2 == 1{
        res[mid][mid] = count
    }
    return res

}

算法总结

  • 有序数组的平方：使用双指针法进行排序
  • 长度最小的子数组：使用滑动窗口对一定范围内的数组进行筛选
  • 螺旋数组II：下标转圈圈，同样是双指针的运用

总结

二分法

左闭右开区间，通过mid来更新 下标指针 的位置

双指针法（快慢指针法）

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

滑动窗口

要理解滑动窗口如何移动窗口起始位置，达到动态更新窗口的大小，从而得出长度最小的符合条件的长度

精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置，从而降低时间复杂度。