双指针与滑动窗口

一、 双指针 (Two Pointers)1. 算法原理双指针的核心思想是利用数组的有序性或特定结构通过两个指针的协同移动通常是相向移动的头尾指针或同向移动的快慢指针将原本可能需要O(n2)O(n^2)O(n2)复杂度的嵌套循环暴力解法降维到O(n)O(n)O(n)复杂度。2. 适用场景处理有序数组或链表中的对撞问题如求和、比大小。字符串/数组的对称性判断如回文串。原地修改数组如移除元素。3. 经典示例与代码示例 1验证回文串 (头尾指针)利用首尾两端的指针向中间靠拢跳过非字母数字字符对比字符是否相等。Python 实现defis_palindrome(s:str)-bool:left,right0,len(s)-1whileleftright:whileleftrightandnots[left].isalnum():left1whileleftrightandnots[right].isalnum():right-1ifs[left].lower()!s[right].lower():returnFalseleft1right-1returnTrueJava 实现publicbooleanisPalindrome(Strings){intleft0,rights.length()-1;while(leftright){while(leftright!Character.isLetterOrDigit(s.charAt(left)))left;while(leftright!Character.isLetterOrDigit(s.charAt(right)))right--;if(Character.toLowerCase(s.charAt(left))!Character.toLowerCase(s.charAt(right)))returnfalse;left;right--;}returntrue;}示例 2两数之和 II - 输入有序数组根据两数之和与目标值的大小关系决定是左指针右移增大和还是右指针左移减小和。Python 实现deftwo_num_sum(nums:list[int],target:int)-tuple[int,int]:l,r0,len(nums)-1whilelr:snums[l]nums[r]ifstarget:return(l,r)elifstarget:r-1else:l1return(-1,-1)二、 滑动窗口 (Sliding Window)1. 算法原理滑动窗口是双指针的“同向升级版”。它使用左右两个指针在数组或字符串上“同向滑动”框定出一个“窗口”。进窗口右指针主动右移扩大窗口并加入新元素。出窗口当窗口满足或破坏特定条件时左指针右移缩小窗口并移出老元素。更新结果在每次窗口变化时记录最优解。2. 适用场景解决连续子数组或子串的问题如求最长/最短的满足条件的子数组。定长子区间的最优解问题。3. 经典示例与代码示例 1长度最小的子数组 (变长窗口 / 弹簧模型)寻找和大于等于 target 的最短连续子数组。Python 实现defmin_sub_array_len(target:int,nums:list[int])-int:left,window_sum,min_len0,0,float(inf)forrightinrange(len(nums)):window_sumnums[right]# 进窗口whilewindow_sumtarget:min_lenmin(min_len,right-left1)window_sum-nums[left]# 出窗口left1returnmin_lenifmin_len!float(inf)else0Java 实现publicintminSubArrayLen(inttarget,int[]nums){intleft0,sum0,minLenInteger.MAX_VALUE;for(intright0;rightnums.length;right){sumnums[right];while(sumtarget){minLenMath.min(minLen,right-left1);sum-nums[left];}}returnminLenInteger.MAX_VALUE?0:minLen;}示例 2长度为 k 的最大子数组和 (定长窗口 / 尺子模型)窗口大小固定整体向右平移。Python 实现defmax_sum_fixed_window(nums:list[int],k:int)-int:current_sumsum(nums[:k])max_sumcurrent_sumforiinrange(k,len(nums)):current_sumcurrent_sumnums[i]-nums[i-k]# 加上新进来的减去滑出去的max_summax(max_sum,current_sum)returnmax_sum三、 工程实战扩展滑动窗口限流器 (Rate Limiting)1. 算法原理与场景在服务端开发中为了防止接口被瞬时高并发压垮需要进行限流。相较于简单的“固定窗口”可能导致的边界突发流量问题滑动窗口限流器按时间维度滑动能更平滑、精确地控制流量。本质上是将空间维度的“数组下标”平移转化为了时间维度的“时间戳”平移。2. 代码示例 (Java 实现)利用队列记录请求的时间戳每次新请求到来时剔除过期的时间戳然后判断当前有效请求数是否超标。Java 实现importjava.util.LinkedList;publicclassSlidingWindowRateLimiter{privatefinallongwindowSizeMillis;privatefinalintmaxRequestCount;privatefinalLinkedListLongwindow;publicSlidingWindowRateLimiter(longwindowSizeMillis,intmaxRequestCount){this.windowSizeMilliswindowSizeMillis;this.maxRequestCountmaxRequestCount;this.windownewLinkedList();}publicsynchronizedbooleantryAcquire(){longcurrentTimeSystem.currentTimeMillis();longboundaryTimecurrentTime-windowSizeMillis;// 1. 窗口平移移除过期时间戳while(!window.isEmpty()window.peekFirst()boundaryTime){window.removeFirst();}// 2. 判断是否超限if(window.size()maxRequestCount){window.addLast(currentTime);returntrue;}returnfalse;}}