1，数组划分

将一组数据划分为不同的区间

解决这一类题用双指针算法，利用数组下标来充当指针

常见的双指针有两种形式，一种是对撞指针，一种是左右指针。

对撞指针：一般用于顺序结构中，也称左右指针。

• 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼 近。

• 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

left == right （两个指针指向同一个位置）

left > right （两个指针错开）

快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

这种方法对于处理环形链表或数组非常有用。

其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。

快慢指针的实现方式有很多种，最常用的一种就是：

• 在一次循环中，每次让慢的指针向后移动一位，⽽快的指针往后移动两位，实现一快一慢

1.1

283. 移动零 - 力扣（LeetCode）

两个指针的作用

1）cur：从左往右扫描数组，遍历数组

2）dest：已处理的区间内，非零元素的最后一个位置

这两个指针就将数组划分为了三个区间：[0,dest] 已经处理过的区间，都是非0元素

, [dest+1,cur-1] 都是0

, [cur,n-1] 没有处理的元素

当cur到n时，数据就处理完成了

过程：

cur从前往后遍历的时候：

1，遇到0，cur++

2，遇到非0，swap（dest+1，cur）; dest++; cur++

class Solution { public void moveZeroes(int[] nums) { for(int cur = 0,dest = -1;cur < nums.length;cur++){ if(nums[cur] != 0){ dest++; int tmp = nums[cur]; nums[cur] = nums[dest]; nums[dest] = tmp; } } } }

1.2 三数之和

15. 三数之和 - 力扣（LeetCode）

解法一：排序+暴力枚举+利用set去重

解法二：排序+双指针

1，排序

2，固定一个数a

3，在该数后面的区间内，利用双指针算法快速找到两个的和等于 -a的即可

处理细节问题：

1，去重

找到一种结果之后，left和right指针要跳过重复元素

当使用完一次双指针算法之后，i 也要跳过重复元素

还需注意避免越界

2，不漏

找到一种结果之后，不要停，缩小区间继续寻找

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ret = new ArrayList<>(); Arrays.sort(nums); int n = nums.length; for(int i = 0;i < n;){ if(nums[i] > 0 ) break; int left = i+1; int right = n-1; int target = -nums[i]; while(left < right){ int sum = nums[left] + nums[right]; if(sum > target){ right--; }else if(sum < target){ left++; } else{ ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right]))); left++; right--; while(left < right && nums[left] == nums[left-1]) left++; while(left < right && nums[right] == nums[right +1]) right--; } } i++; while(i<n && nums[i] == nums[i - 1]) i++; } return ret; } }

2，滑动窗口

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

方法一，暴力枚举出所有的子数组的和

方法二，利用单调性，使用“同向双指针”来优化 ---滑动窗口

1，先初始化left = 0，right= 0

2，进窗口

3，判断 是否出窗口

更新结果（根据题目判断什么时候更新结果）

滑动窗口的时间复杂度为O（n），因为只是挪动了两遍左右指针，n+n=2n

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

76. 最小覆盖子串 - 力扣（LeetCode）

一，暴力解法：哈希表 + 暴力枚举（用滑窗口加双指针来进行优化）

用两个哈希表，1号哈希表hash1 用来记录子串的信息，2号哈希表hash2用来记录目标串 t 的信息

然后实现一个接口函数，判断当前窗口是否满足要求

用 i 遍历两个哈希表中对应位置的元素

如果 t 中某个字符的数量大于窗口字符的数量，也就是2号哈希表某个位置大于1号哈希表，说明不匹配，返回false

如果全都匹配，返回true

在主函数中，先将 t 的信息放入2号哈希表中

初始化一些变量：左右指针：left = 0，right = 0；目标子串的长度：len = INT_MAX；目标子串的起始位置：retleft （通过目标子串的起始位置和长度，就可以找到结果）

当right小于字符串s的长度时，一直下列循环

1，将当前遍历到的元素丢到1号哈希表中

2，检测当前窗口是否满足条件

如果满足条件：

判断当前窗口是否变小。如果变小则更新长度，以及字符串的起始位置retleft也进行更新

判断完毕后，将左侧元素滑出窗口，顺便更新1号哈希表

重复上面两个过程，直到窗口不满足条件

3，right++，遍历下一个元素

判断len的长度是否等于INT_MAX

如果相等，说明没有匹配，返回空字符串

如果不相等，说明匹配，返回s中从retleft位置往后len长度的字符串

优化：优化判断条件

使用count标记有效字符串的种类

1，进窗口的时候：进之前，当hash2（in）== hash1（in），count++

2，出窗口的时候：出之前，当hash2（out）== hash1（out），count--

3，判断条件的时候：count == hash1.size（）

class Solution { public String minWindow(String ss, String tt) { char[] s = ss.toCharArray(); char[] t = tt.toCharArray(); //用数组模拟哈希表 int[] hash1 = new int[128];//用于统计字符串 t 中字符的频次 int kinds = 0;//用于标记字符串t中，有多少种字符 for(char ch : t) { if(hash1[ch]++ == 0) kinds++; } int[] hash2 = new int[128];//统计窗口中字符的出现频次 int len = Integer.MAX_VALUE,begin = -1; for(int left = 0,right = 0,count = 0;right < s.length;right++){ char in = s[right]; if(++hash2[in] == hash1[in]) count++; while(kinds == count){ //更新结果 if(right-left+1 < len){ begin = left; len = right-left+1; } //出窗口 char out = s[left++]; if(hash2[out] == hash1[out]) count--; hash2[out]--; } } if(begin == -1) return new String(); else return ss.substring(begin,begin+len); } }