力扣爆刷第135天之数组五连刷（双指针快慢指针滑动窗口）

力扣爆刷第135天之数组五连刷（双指针快慢指针滑动窗口）

一、704. 二分查找

题目链接：https://leetcode.cn/problems/binary-search/description/
思路：经典二分查找算法，每次与中值比较，中值大于target右边界左移，中值小于target左边界右移。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
            }else if(nums[mid] > target) {
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
}

二、27. 移除元素

题目链接：https://leetcode.cn/problems/remove-element/description/
思路：移出相同元素，经典快慢指针，元素不等慢指针才走。

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != val) {
                nums[slow++] = nums[i];
            }
        }
        return slow;
    }
    
}

三、977. 有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/description/
思路：画了一个非常清晰易懂的图，对含有负数的有序数组进行平方之后的排序，其实平方后就是第二个图形，只需要双指针从两端进行归并排序即可。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int len = nums.length, left = 0, right = len-1;
        int[] result = new int[len];
        for(int i = 0; i < len; i++) {
            nums[i] *= nums[i]; 
        }
        int k = right;
        while(left <= right) {
            if(nums[left] > nums[right]) {
                result[k--] = nums[left++];
            }else{
                result[k--] = nums[right--];
            }
        }
        return result;
    }
}

四、209. 长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/description/
思路:求满足目标和的最短长度子数组，这种题目一看就是滑动窗口，使用快慢指针，快指针扩大窗口，慢指针缩小窗口。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length, min = len+1, sum = 0, slow = 0, fast = 0;
        while(fast < len) {
            sum += nums[fast++];
            while(sum >= target) {
                min = Math.min(min, fast - slow);
                sum -= nums[slow++];
            }
        }
        return min == len+1 ? 0 : min; 
    }
}

五、59. 螺旋矩阵 II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/description/
思路：螺旋矩阵非常经典的题目，分别控制四个边界即可。

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int k = 1, sum = n * n;
        int left = 0, right = n, up = 0, down = n;
        while(k <= sum) {
            if(up < down) {
                for(int i = left; i < right; i++) {
                    nums[up][i] = k++;
                }
                up++;
            }

            if(left < right) {
                for(int i = up; i < down; i++) {
                    nums[i][right-1] = k++;
                }
                right--;
            }

            if(up < down) {
                for(int i = right-1; i >= left; i--) {
                    nums[down-1][i] = k++;
                }
                down--;
            }

            if(left < right) {
                for(int i = down-1; i >= up; i--) {
                    nums[i][left] = k++;
                }
                left++;
            }
        }
        return nums;
    }
}