这是一道比较典型的数组题,题目本身不复杂,但面试官通常更关注你能不能快速判断数据特点,并选择合适的解法。
Find sub range in a list of numbers that add up to target.
给定一个数字数组 nums 和目标值 target,找到数组中的一个连续子区间,使得这个区间内所有数字之和恰好等于 target,返回区间的起始和结束位置。
例如:
nums = [1, 2, 3, 7, 5]
target = 12
输出:
[1, 3]因为:
nums[1...3] = [2, 3, 7]
2 + 3 + 7 = 12如果题目明确数组里都是正数,可以考虑 Sliding Window(滑动窗口)。
维护左右两个指针和当前窗口的总和。总和小于 target 时向右扩展;大于 target 时移动左指针缩小窗口;等于 target 时就找到了答案。
这种情况下时间复杂度可以做到 O(n)。
不过面试时要特别注意一个细节:数组里是否允许出现负数。
如果包含负数,滑动窗口就不一定成立,因为扩大窗口之后总和不一定增加,缩小窗口之后也不一定减少。这时候通常会转向:
Prefix Sum + HashMap
通过记录之前出现过的前缀和,判断是否存在:
currentPrefixSum - target如果存在,就说明中间这一段连续数组的和正好是 target。
CSOAHELP 面试辅助
如果你正在准备 Atlassian、Google、Amazon、Stripe、TikTok 等公司的技术面试,CSOAHELP 可以提供 Mock Interview 和 实时文本面试辅助。
真实面试中遇到题目后,可以帮助快速整理题意、分析思路、识别 follow-up,并辅助组织英文表达。重点不是背固定答案,而是在有限时间里更清楚地展示自己的解题过程。
