文章目录
- 双指针
- 对撞指针
- 快慢指针
- 滑动窗口
双指针
双指针：指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。
如：二分查找就是使用的双指指针
对撞指针
对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。
案例一：返回有序数组arr中查找 和为目标target的两个值的下标
functionsum(arr,target){letleft=0,right=arr.length-1;while(left<right){if(arr[left]+arr[right]>target){right--;}elseif(arr[left]+arr[right]<target){left++;}elseif(arr[left]+arr[right]==target){return[left,right];}}}案例二:数组反转
functionreverse(arr){letleft=0,right=arr.length-1;while(left<right){[arr[left],arr[right]]=[arr[right],arr[left]];left++;right--;}returnarr;}快慢指针
快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。
案例：压缩字符串
输入：ddddaaayhuuaaa 输出：d4a3y1h1u2a3functioncompressString(string){// j指针表示的是遍历字符串的指针，i指针指向的是当前计数对应的字母指针letnewS="",i=0,j=0;while(j<string.length-1){if(string[j]!==string[j+1]){newS+=string[i]+(j-i+1);i=j+1;}j++;}newS+=string[i]+(j-i+1);returnnewS;}滑动窗口
滑动窗口算法是一种解决数组或列表中子数组或子序列问题的有效方法。
该算法通过定义一个窗口，然后在数据结构上滑动该窗口，逐步处理数据，以解决特定类型的问题。其基本思想是维护一个窗口，初始时窗口覆盖数组中的一部分元素，然后通过滑动窗口来依次处理每个子数组。在每次窗口滑动时，可以通过添加新元素和删除旧元素来更新窗口的内容，以在O(1)时间内完成操作。
滑动窗口实际上是双指针算法的一个延伸，它特指双指针算法中的同向双指针。
案例：
给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 子数组[numsl,numsl+1,...,numsr-1,numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。 示例 ： 输入：target=7,nums=[2,3,1,2,4,3]输出：2解释：子数组[4,3]是该条件下的长度最小的子数组。题解：
/** * @param {number} target * @param {number[]} nums * @return {number} */varminSubArrayLen=function(target,nums){letleft=0;letright=0;letsum=0;letmin=Infinity;while(right<nums.length){sum+=nums[right];if(sum>=target){while(sum>=target&&left<=right){sum-=nums[left];left++;}// 这里+2是因为while循环中多运行了一次min=Math.min(min,right-left+2);}right++;}returnmin===Infinity?0:min;};
