数组：二分查找、移除数组等经典数组题

二分查找：

相关题目链接：https://leetcode.cn/problems/binary-search/

题目重现：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路：

首先，要在n个升序整型数组nums中找到一个确定的值，我们首先想到的肯定是暴力求解：将数组中的每个元素都遍历一遍然后与目标值进行对比。但当n值很大且目标值不存在于数组中时，这个方法是非常不好的。

要想简单去解决这个问题，我们需要用到二分法。

当然二分法是有使用前提的：

1.数组为有序数组

2.数组中无重复元素。

二分法有一个重难点，那就是如何确定区间。

区间有：

[i，j) 左闭右开区间

(i，j] 左开右闭区间

[i，j] 左闭右闭区间

闭区间表示这个区间中包括这个数，开区间表示这个区间中不包括这个数。

举个例子：(2，5] 这个区间是左开右闭区间，在这个区间中，所有的整数有3，4，5。其中不包括2，而5是这个区间的边沿。

区分好各种区间应该包括哪些数，下面我们来说这道题的重点：二分法

顾名思义，二分法就是把当前的区间从中间分成两个部分，然后逐步细分直到我们得出我们想要的东西。

例如：当前我们有这样一个数组，我们想要找到5这个数字是否在数组中。

如果，当前中间数下标为i。

那么存在：

• if（nums[i]==target） 表示，当前i下标的值就是要找的特定值。

• if（nums[i] < target）表示，特定值只可能在当前i下标之后的区间中。

• if（nums[i] > target）表示，特定值只可能在当前i下标之前的区间中

也就是说，我们首先在[left,right]这个区间中找特定值，在这个区间中，我们得到这个区间的中间下标与特定值进行对比，然后逐渐缩小我们要查找的区间，直到找到这个特定值，或查找区间为空。

代码：

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

移除数组：

相关题目链接：https://leetcode.cn/problems/remove-element/

题目重现：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路：

我们将这道题拆分下来也就是说，这道题我们要找到数值等于val的元素，然后移除它们，并返回数组的新长度。

要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

这里，我们可以使用双指针的方式：

• 快指针：寻找新数组的元素 ，新数组中不含有目标元素。

• 慢指针：指向更新，新数组下标的位置。

代码：

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

有序数组的平方：

相关题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

题目重现：

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

思路：

我这里采用了暴力解法，也就是遍历数组中每一个元素，然后将其平方。最后将平方后的数组进行排序。当然这里也可以采用双指针的写法。

代码：

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

长度最小的子数组：

相关题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

题目重现：

给定一个含有 n 个正整数的数组和一个正整数 target 。

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

思路：

这里可以采用暴力解法。也可以采用滑动窗口的解法。我这里采用了滑动窗口的解法。

滑动窗口也就是说：就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

定义两个指针 start 和 end 分别表示子数组也就是滑动窗口的开始位置和结束位置。

其次，我们需要一个变量 sum来存储子数组中的元素和。

在初始状态下，start 和 end 都指向下标 0，sum的值为 0。

每一轮迭代，将 nums[end]加到 sum，如果 sum≥s，则更新子数组的最小长度，然后将 nums[start] 从 sum 中减去并将 start 右移，直到 sum<s，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 end 右移。

代码：

class Solution {public int minSubArrayLen(int target, int[] nums) {int i=0;int n=nums.length;int sum=0;if(n==0){return 0;}int ans=Integer.MAX_VALUE;for (int j = 0; j <n; j++) {sum+=nums[j];while(sum>=target) {ans = Math.min(ans, j - i + 1);sum -= nums[i++];}}return ans == Integer.MAX_VALUE ? 0 : ans;}
}

螺旋矩阵Ⅱ：

相关题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

题目重现：

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

思路：

这道题我们要明确：循环不变量原则。

首先，我们模拟一下顺时针画矩阵的过程:

• 填充上行从左到右

• 填充右列从上到下

• 填充下行从右到左

• 填充左列从下到上

此时，我们发现，我们需要一圈一圈的循环，如果这个循环中不固定循环的规则的话，我们很有可能写着写着就懵逼了。

所以，这个时候，我们先确定一下循环的规则，在这里我确定的规则是：左闭右开。

那么根据，这个规则，我们就可以很容易的写出循环代码了。

代码:

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