Leetcode刷题-数组（二分法、双指针法、窗口滑动）

数组

1、二分法

704. 二分查找 - 力扣（LeetCode）

需要注意区间的问题。首先在最外面的循环判断条件是left<=right。那就说明我们区间规定的范围就是【left,right】

属于是左闭右闭！！！！！！

那之后在判断target和我们数组中的num [ mid ] 大小关系之后，再重新调整right，以及left的时候，应该是left = mid + 1，right = mid - 1

while (left <= right) 要使⽤ <= ，因为left == right是有意义的
所以使⽤ <= if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]⼀定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

2、移除元素（双指针-同向）

27. 移除元素 - 力扣（LeetCode）

除了可以暴力两层循环这么去从后往前覆盖，从而消除掉目标元素

还可以使用双指针法：快慢指针（重点是理解快慢指针什么含义）！！！！！！！！

快指针：遍历数组，去寻找新数组的元素，就是通过这个指针去找出来，除了目标元素的所有值
慢指针：用于指向新数组的下标，就是通过快指针找到符合条件的元素（不是需要删除的元素）就将其放进“新数组”，慢指针指向的下标就会+1

int slow = 0;
for(int fast = 0; fast < nums.length; fast++){
    if(nums[fast] != target){
        nums[slow++] = nums[fast];
    }
}

3、有序数组的平方（双指针-相向）

题目需求：一个有序数组，存在有负数，所有元素依次取平方要求最后还是有序

977. 有序数组的平方 - 力扣（LeetCode）

根据题意可以知道，最大值肯定出现在数组的左右两侧

所以还是想到用双指针的思路，两个指针分别指向数组的开头和结尾，然后向中间移动

符合条件的放进新的数组中

public int[] sortedSquares(int[] nums) {
    int k = nums.length - 1;    
    int[] res = new int[k+1]; 		//注意数组长度定义
    for(int i=0,j=k; 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;
}

4、⻓度最⼩的⼦数组（滑动窗口）

209. 长度最小的子数组 - 力扣（LeetCode）

在这里插入图片描述

除了暴力解决，还有滑动窗口思路

其实也就是双指针的思路，不过是取两个指针中间的一个集合，像是一个滑动的窗口

最后目标的长度就是：指针2 - 指针1 + 1

然后需要明确一下两个指针的含义：

指针1：for循环里面的指针 j ，这个是指向这个区间的终止位置的，我们的目标是通过对开始位置指针i 进行操作然后更新最小长度
指针2：这个用来标记开始位置，和指针1结合使用

1、窗⼝的起始位置如何移动：如果当前窗⼝的值⼤于s了，窗⼝就要向前移动了（也就是该缩⼩了）。

2、**窗⼝的结束位置如何移动：**窗⼝的结束位置就是遍历数组的指针，也就是for循环⾥的索引。

解题的关键在于 窗⼝的起始位置如何移动，相当于是sum一边吐出之前区间中最开始的数据，然后再加上一下个数据，之后再利用标记开始位置的指针2，再取判断

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0;    // 滑动窗⼝起始位置，也就是指针2
        int sum = 0;  // 滑动窗⼝数值之和
        int minLen = Integer.MAX_VALUE;  
        for(int j = 0; j < nums.length; j++){
            sum += nums[j];
            while(sum >= target){
                int len = j - i + 1;
                minLen = Math.min(minLen,len);
                sum -= nums[i]; // 这⾥体现出滑动窗⼝的精髓之处，不断变更i（⼦序列的起始位置）
                i++;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;  // 如果result没有被赋值的话，就返回0，说明没有符合条件的⼦序列
    }
}

5、螺旋矩阵II (知道思路即可，有空再练代码)

59. 螺旋矩阵 II - 力扣（LeetCode）

在这里插入图片描述

⾯试中出现频率较⾼的题⽬，本题并不涉及到什么算法，就是模拟过程，但却⼗分考察对代码的掌控能⼒。

这里容易遇到的问题是：

就是因为在画每⼀条边的时候，⼀会左开右闭，⼀会左闭右闭，⼀会⼜来左闭右开，岂能不乱。

比如第一次是1、2、3，第二次遍历第二条边又成了4、5，不包含起始节点了，这样就很乱，肯定会出问题

int[][] res = new int[n][n]; // 使⽤vector定义⼀个⼆维数组
int startx = 0, starty = 0; // 定义每循环⼀个圈的起始位置
int loop = n / 2; // 每个圈循环⼏次，例如n为奇数3，那么loop = 1 只是循环⼀圈，矩阵中间的值需要单独处理
int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
int count = 1; // ⽤来给矩阵中每⼀个空格赋值
int offset = 1; // 需要控制每⼀条边遍历的⻓度，每次循环右边界收缩⼀位
int i,j;
while (loop > 0) {
    i = startx;
    j = starty;
    // 下⾯开始的四个for就是模拟转了⼀圈
    // 模拟填充上⾏从左到右(左闭右开)
    for (j = starty; j < n - offset; j++) {
        res[startx][j] = count++;
    }
    // 模拟填充右列从上到下(左闭右开)
    for (i = startx; i < n - offset; i++) {
        res[i][j] = count++;
    }
    // 模拟填充下⾏从右到左(左闭右开)
    for (; j > starty; j--) {
        res[i][j] = count++;
    }
    // 模拟填充左列从下到上(左闭右开)
    for (; i > startx; i--) {
        res[i][j] = count++;
    }
    // 第⼆圈开始的时候，起始位置要各⾃加1， 例如：第⼀圈起始位置是(0, 0)，第⼆圈起始位置是(1, 1)
    startx++;
    starty++;
    // offset 控制每⼀圈⾥每⼀条边遍历的⻓度
    offset += 1;
    loop--;
}
// 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
if (n % 2 != 0) {
    res[mid][mid] = count;
}
return res;