leetCode-hot100-数组专题之双指针

双指针在算法题中很常见，下面总结双指针在数组中的一些应用，主要分为两类：

1.同向双指针

题目中有原地、不适用额外空间等关键词，一般解决方法是定义两个快慢指针：
快指针：用来遍历数组，并进行一些规则匹配
慢指针：用来表示结果数组，即当前符合条件的数组

最后一般是返回慢指针的下标，需要注意的是有时候不能只返回慢指针的下标，可能需要+1，需要根据实际情况分析。

1.1例题

26.删除有序数组中的重复项

思路：
本题设置一个辅助下标指针idx指向数组的第一个元素，然后往后遍历数组，如果遇到了相同的元素就跳过，遇到不同的元素则加入到辅助下标的后一个元素，依次类推，直到遍历数组结束，最后返回idx+1即为所求的长度。详细的视频讲解点击视频讲解-删除有序数组中的重复项。
时间复杂度：
时间复杂度为O(n)，只进行了一次数组的遍历。
代码实现：

class Solution {public int removeDuplicates(int[] nums) {if(nums.length < 2) return nums.length;int idx = 0;for(int i = 1;i < nums.length;i++){if(nums[i] != nums[idx]){idx = idx + 1;nums[idx] = nums[i];}}return idx + 1;}
}

27.移除元素

思路：
本题的思路和第26题一样，需要一个辅助下标idx，遍历整个数组，当遇到数组元素不等于val时，则将其加入到删除后的数组中，同时辅助下标后移，遍历结束后返回辅助下标idx的值即可，详细的视频讲解点击视频讲解-移除元素。
时间复杂度：
时间复杂度为O(n)，n为数组的长度。
代码实现：

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

80.删除有序数组中的重复项 Ⅱ

思路：
本题采用双指针来求解，解法和26.删除有序数组中的重复项类似，但是由于本题中每个元素可以出现两次，所以将idx设置为1，设置前两个位置为结果数组，第二个指针从索引为2开始，比较当前元素和结果数组中的倒数第二个元素的值是否相等（即nums[idx - 1]，注意这里不要使用nums[--idx]，因为这样会改变idx的值，导致索引不正确），如果相等则i++，继续向后遍历，如果不相等则加入到结果数组中（这里可以这样做的原因是nums是有序数组！！！如果是无序数组则不能这么做），下面是一个模拟的例子：

视频讲解点击视频讲解-删除有序数组中的重复项 Ⅱ
时间复杂度：
时间复杂度为O(n)，其中n为数组的长度。
代码实现：

class Solution {public int removeDuplicates(int[] nums) {if(nums.length <= 2) return nums.length;int idx = 1;for(int i = 2;i < nums.length ; i++){if(nums[i] != nums[idx - 1]){nums[++idx] = nums[i];}}return idx + 1;}
}

2.相向双指针

双指针 一般是一个在开头，一个在结尾，两者相向处理问题，一般用来确定某个符合条件的子数组，需要维护左右边界。

2.1例题

11.盛最多水的容器

思路：
本题采用双指针来求解，由于盛水的体积为宽✖高，因此可以定义首尾两个指针，枚举出不同高度的体积并取最大值，在移动指针的过程中，应该移动高度较小的指针，因为盛水的高度是由短板来决的，如图，不同的颜色表示每次移动指针后得到的体积。视频讲解点击视频讲解-盛最多水的容器。

时间复杂度：
时间复杂度为O(n)，空间复杂度O(1)。
代码实现：

class Solution {public int maxArea(int[] height) {int ans = 0;int l = 0;int r =height.length - 1;while(l < r){ans = Math.max(ans,Math.min(height[l],height[r]) * (r-l));if(height[l] < height[r]) l++;else r--;}return ans;}
}

42.接雨水

思路：
本题采用双指针来求解，类似于11.盛水最多的容器，盛水的多少取决于左右柱子里较低的一个。通过维护左边和右边的最大高度，来计算整个数组中的装水容量，定义两个变量lmax和rmax，初始值都为0，用于记录当前位置左边和右边的最大高度，不断更新左右两边的最大高度来计算每个位置的水位，然后将各个位置的水位差累加起来得到总的装水容量，下面是一个模拟的例子：

视频讲解点击视频讲解-接雨水。
时间复杂度：
这段代码的时间复杂度是O(n)，其中n是height数组的长度。由于只使用了一个while循环来遍历height，没有嵌套的循环，因此时间复杂度是线性的。
代码实现：

class Solution {public int trap(int[] height) {int l = 0;int r = height.length - 1;int lmax = 0;int rmax = 0;int ans = 0;while(l < r){lmax = Math.max(lmax,height[l]);rmax = Math.max(rmax,height[r]);if(lmax < rmax){ans += lmax - height[l];l++;} else{ans += rmax - height[r];r--;}}return ans;}
}

581.最短无序连续子数组

思路：
本题采用双指针解决，分别从数组的两端进行遍历，确定结果数组的左右边界。确定左边界的条件如果当前元素小于左边界处的最大值，则更新右边界，否则更新左边界的最大值（左边界的右边不应该出现比左边界小的值）；确定右边界的条件是如果当前元素大于右边界处的最小值，则更新左边界，否则更新右边界的最小值（右边界的左边不应该出现比右边界大的值），得到左右边界后返回子数组的长度即可。
时间复杂度：
时间复杂度为O(n)，n为数组长度。
代码实现：

class Solution {public int findUnsortedSubarray(int[] nums) {//初始化工作：//start、end分别是从前向后和从后向前遍历数组的两个指针//需要注意的是end不是从len - 1开始，初始值应该为-1，这是为了处理数组本来就是有序数组的情况//lmax、rmin分别是遍历过程中维护的左边界的最大值和右边界的最小值int len = nums.length;int start = 0;int end = -1;int lmax = nums[0];int rmin = nums[len - 1]; for(int i = 0;i < len ; i++){//确定左边界if(nums[i] < lmax){end = i;} else {lmax = nums[i];}//确定右边界if(nums[len - i - 1] > rmin){start = len - i -1;} else {rmin = nums[len - i -1];}}return end - start + 1;}
}

参考资料：双指针-数组