双指针，滑动窗口

1数组划分将一组数据划分为不同的区间解决这一类题用双指针算法利用数组下标来充当指针常见的双指针有两种形式一种是对撞指针一种是左右指针。对撞指针一般用于顺序结构中也称左右指针。• 对撞指针从两端向中间移动。一个指针从最左端开始另一个从最右端开始然后逐渐往中间逼 近。• 对撞指针的终止条件一般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是left right 两个指针指向同一个位置left right 两个指针错开快慢指针又称为龟兔赛跑算法其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使用快慢指针的思想。快慢指针的实现方式有很多种最常用的一种就是• 在一次循环中每次让慢的指针向后移动一位⽽快的指针往后移动两位实现一快一慢1.1283. 移动零 - 力扣LeetCode两个指针的作用1cur从左往右扫描数组遍历数组2dest已处理的区间内非零元素的最后一个位置这两个指针就将数组划分为了三个区间[0,dest] 已经处理过的区间都是非0元素, [dest1,cur-1] 都是0, [cur,n-1] 没有处理的元素当cur到n时数据就处理完成了过程cur从前往后遍历的时候1遇到0cur2遇到非0swapdest1cur; dest; curclass 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固定一个数a3在该数后面的区间内利用双指针算法快速找到两个的和等于 -a的即可处理细节问题1去重找到一种结果之后left和right指针要跳过重复元素当使用完一次双指针算法之后i 也要跳过重复元素还需注意避免越界2不漏找到一种结果之后不要停缩小区间继续寻找class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger ret new ArrayList(); Arrays.sort(nums); int n nums.length; for(int i 0;i n;){ if(nums[i] 0 ) break; int left i1; 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 ArrayListInteger(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(in nums[i] nums[i - 1]) i; } return ret; } }2滑动窗口209. 长度最小的子数组 - 力扣LeetCode方法一暴力枚举出所有的子数组的和方法二利用单调性使用“同向双指针”来优化 ---滑动窗口1先初始化left 0right 02进窗口3判断 是否出窗口更新结果根据题目判断什么时候更新结果滑动窗口的时间复杂度为On因为只是挪动了两遍左右指针nn2nclass 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-left1); 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 0right 0目标子串的长度len INT_MAX目标子串的起始位置retleft 通过目标子串的起始位置和长度就可以找到结果当right小于字符串s的长度时一直下列循环1将当前遍历到的元素丢到1号哈希表中2检测当前窗口是否满足条件如果满足条件判断当前窗口是否变小。如果变小则更新长度以及字符串的起始位置retleft也进行更新判断完毕后将左侧元素滑出窗口顺便更新1号哈希表重复上面两个过程直到窗口不满足条件3right遍历下一个元素判断len的长度是否等于INT_MAX如果相等说明没有匹配返回空字符串如果不相等说明匹配返回s中从retleft位置往后len长度的字符串优化优化判断条件使用count标记有效字符串的种类1进窗口的时候进之前当hash2in hash1incount2出窗口的时候出之前当hash2out hash1outcount--3判断条件的时候count hash1.sizeclass 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-left1 len){ begin left; len right-left1; } //出窗口 char out s[left]; if(hash2[out] hash1[out]) count--; hash2[out]--; } } if(begin -1) return new String(); else return ss.substring(begin,beginlen); } }