51mee - AI智能招聘平台Logo
模拟面试题目大全招聘中心会员专区

给定一个整数数组nums和一个整数target,返回所有和为target的连续子数组的索引范围(左闭右闭)。例如nums=[1,2,3,4,5],target=9,结果为[2,4]。请实现一个时间复杂度为O(n)的算法。

微软Software Engineer Intern难度:中等

答案

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时左指针移动的情况:若sum超过target,未移动左指针,会导致后续无法找到更小的和为target的子数组,漏掉结果。
  • 记录结果时未更新左指针:当sum==target时,只记录当前left和right,但后续移动right后sum变化,若未移动left,可能导致重复记录或遗漏。
  • 初始sum处理错误:初始sum设为0,当nums[0]==target时,需正确记录结果,否则会漏掉第一个子数组。
  • 数组为空或无解时的处理:需返回空列表,避免越界错误。
  • 时间复杂度分析错误:误认为滑动窗口需要多次遍历数组,导致时间复杂度分析错误,实际每个元素最多被处理两次(加入和移出),故为O(n)。
51mee.com致力于为招聘者提供最新、最全的招聘信息。AI智能解析岗位要求,聚合全网优质机会。
产品招聘中心面经会员专区简历解析Resume API
联系我们南京浅度求索科技有限公司admin@51mee.com
联系客服
51mee客服微信二维码 - 扫码添加客服获取帮助
© 2025 南京浅度求索科技有限公司. All rights reserved.
公安备案图标苏公网安备32010602012192号苏ICP备2025178433号-1