那些可以用双指针解决的题目
- 什么时候用双指针，该咋用？
-
- 双指针思想
-
- 35.搜索插入位置
- 27.移除元素
- 209，长度最小的子数组
什么时候用双指针，该咋用？
双指针思想
双指针是我们做题中经常用到的思想，所以这个在刷题初期是一定要会的。其实我们早就学习过这个方法，我们通过二分查找来描述一下这个思想。
二分查找首先定义两个指针，左指针和右指针，分别指向数组的头和尾，然后计算出他俩的中间的索引，其值和目标值进行比较，如果目标值更大则说明目标值在中间索引和右指针中间，则需要移动左指针到中间索引的后一位。如果目标值比中间值小，则需要移动右指针到中间索引的前一位。不断执行，直至找到目标值，或当该数组不含有目标值，左指针和右指针重合时跳出该循环。
二分查找代码
public static int halfnum(int[] arraynum ,int b){
int hi =arraynum.length-1;
int lo = 0;
//先判断数组是不是空
if (arraynum.length==0){
return -1;
}
while(hi>=lo){
//判断是否等于要猜的数
if(b==arraynum[(hi+lo)/2]){
return (hi+lo)/2;
}
//大于中间数的情况
else if (b>arraynum[(hi+lo)/2]){
lo= (hi+lo)/2+1;
}
//小于中间数的情况
else{
hi=(hi+lo)/2-1;
}
}
return -1;
}
35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
题目很好理解，但是我们想要一次AC是不太容易的。我们根据题意可以想到，这样共有四种可能
插入情况无非就这几种
（1）比数组里的任何值都小，插入头部
（2）比数组里的任何值都大，插入尾部
（3）查询到数组元素，返回该处索引值
（4）数组内无该元素，将其插入两元素之间。
所以我们可以通过以下代码实现该题
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
//中间值，与target对比
int mid = (left + right) / 2;
//第三种情况
if(nums[mid] == target) {
return mid;
//移动左指针
} else if(nums[mid] < target) {
left = mid + 1;
} else {
//移动右指针
right = mid - 1;
}
}
//1，2，4三种情况都在循环内部，我们只需输出左指针即可。
return left;
}
}
刚才我们说了双指针思想的重要性，下面这个题目也是可以完全通过双指针思想实现的，所以说双指针的思想是必须有的。你可以通过下面这个题目完全体会到双指针的重要性
27.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
该题目我们可以创建两个指针，一前一后，前面的负责探路后面的负责填充，当前面查询到需要移除的元素时直接跳过该元素，继续前进。后面的指针只负责往该数组里面填充不需要移除的数字。所以我们可以根据以下代码实现
class Solution {
public int removeElement(int[] nums, int val) {
//特殊情况
if(nums==null){
return 0;
}
int j = 0;//慢指针，i代表快指针
for(int i = 0;i<nums.length;i++){
//正常情况直接赋值给i
if(nums[i]!=val){
nums[j]=nums[i];
j++;
}
//如果为需要删除的值时，则快指针移动，慢指针不动。
}
return j;
}
}
刚才我们学习了两个双指针的题目，是不是对这个做题思想有了一些理解了，下面我们来使用一个更加高级的双指针，这个也是经常使用的思想，但是归根结底还是双指针思想。
该题目的思想也是双指针的思想，不过这个代码比较难写一些，用到的情况也是比较多的，所以我们这个题目要用心体会一下。
209，长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组
题目含义比较好理解，则是在数组里面找出长度最小的子数组，子数组的元素和大于等于目标值。这个题目我们就用到了滑动窗口的思想。
滑动窗口：就是通过不断调节子数组的起始位置和终止位置，进而得到我们想要的结果我们也可以看成是双指针的一种。
在该题中，我们可能遇到这种情况 大家思考一下，数组的值是1，2，3，4，5我们的s为5，所以我们第一次的子数组（滑动窗口）长度则为3，1+2+3>5,这时左指针在1的位置，右指针在3的位置，但是2+3=5同样符合，所以我们就需要移动左指针，此时窗口长度则改为2了。然后我们保留该值，继续移动左指针，判断3是否仍符合，此时发现不符合了，则需要移动右指针，移动到下一个符合情况的元素，继续执行刚才的步骤，直到数组的最后。所以整个过程中滑动窗口的长度变化为，3,2,3,2,3,2,1，最小的则为1.
我们可以通过以下代码解决该题。
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int chiledlen = Integer.MAX_VALUE;
int winlen = 0;//窗口大小
int sum = 0;
int i = 0;//起始长度位置
for(int j = 0 ; j < nums.length;j++){
sum += nums[j];
//发现符合条件的情况
//循环内部的代码是精髓所在
while(sum>=s){
winlen = j-i+1;
chiledlen = Math.min(chiledlen,winlen);
//下面两行是滑动窗口的意义所在，改变起点位置，判断是否仍符合条件
sum-=nums[i];
i++;
}
}
return chiledlen == Integer.MAX_VALUE ? 0:chiledlen;
}
}
通过以上三个题目我们是不是对双指针思想有了一些理解了，该思想不仅可以用在数组的题目上，链表同样适用。所以我们要完全掌握，这三个题目大家有时间的话还是自己动手做一下。
