
1) 【一句话结论】:使用滑动窗口(双指针)技术,通过动态调整窗口左右边界维护当前子数组和,遍历数组时记录所有和为target的连续子数组索引范围,时间复杂度为O(n)。
2) 【原理/概念讲解】:滑动窗口是一种高效处理连续子数组问题的技术,核心是利用左右指针维护一个窗口,窗口内的元素和为当前子数组和。初始时左指针left=0,窗口和sum=0。遍历右指针right从0到n-1,每次将nums[right]加入sum。若sum等于target,则记录当前left和right作为结果;若sum超过target,则移动左指针left,直到sum≤target(每次左指针右移时,sum减去nums[left])。由于每个元素最多被加入和移出窗口一次,因此时间复杂度为O(n)。类比:就像滑滑梯,左右指针是滑梯两端,移动时调整“高度”(和),当高度等于目标时,就记录当前位置。
3) 【对比与适用场景】:
| 方法 | 定义 | 时间复杂度 | 使用场景 | 注意点 |
|---|---|---|---|---|
| 暴力解法 | 双重循环遍历所有可能的子数组,计算和 | O(n²) | 数组规模小,或对时间复杂度要求不严格 | 容易超时 |
| 滑动窗口 | 利用左右指针维护连续子数组和,动态调整窗口 | O(n) | 连续子数组求和,尤其是数组元素为正数时 | 需要处理和超过target的情况 |
4) 【示例】:
数组nums=[1,2,3,4,5],target=9。
left=0,sum=0。right=0:sum=1<9,right++。right=1:sum=3<9,right++。right=2:sum=6<9,right++。right=3:sum=10>9,移动left=1,sum=10-1=9==target,记录[1,3]。right=4:sum=9+4=13>9,移动left=2,sum=13-2=11>9,移动left=3,sum=11-3=8<9,right=4,sum=8+5=13>9,无更多结果。[1,3](对应子数组[2,3,4]和9)。5) 【面试口播版答案】:
“这道题要找所有和为target的连续子数组索引范围,时间复杂度要求O(n)。核心思路是滑动窗口(双指针)。我们用左指针left和右指针right维护一个窗口,初始和为0。遍历右指针right,每次将nums[right]加入窗口和sum。如果sum等于target,就记录当前left和right作为结果。如果sum超过target,就移动左指针left,直到sum≤target。这样每个元素最多被加入和移出窗口一次,时间复杂度O(n)。”
6) 【追问清单】:
nums[left],直到sum≤target,此时记录结果。sum==target时,记录当前left和right,然后继续移动right,此时sum会加上新元素,若超过target则移动left,不会重复记录,因此不会遗漏。7) 【常见坑/雷区】:
sum超过target,未移动左指针,会导致后续无法找到更小的和为target的子数组,漏掉结果。sum==target时,只记录当前left和right,但后续移动right后sum变化,若未移动left,可能导致重复记录或遗漏。sum设为0,当nums[0]==target时,需正确记录结果,否则会漏掉第一个子数组。