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