给一个长度为 n 的整数数组和一个整数 k，求最长的连续子数组，使得其元素和 ≤ k。先回答：当数组元素全部为非负整数时你怎么做？再回答：如果数组里可能出现负数，原来那套滑动窗口还成不成立、为什么、你会改用什么做法？

面试官在考什么

判断候选人是把滑动窗口当模板背，还是真理解它成立所依赖的单调性前提——这是区分高低最明显的一题。

滑动窗口

回答框架 · 前两步

1. 非负版本：右指针 r 一路右移累加 sum；当 sum > k 时循环左移 l 直到 sum ≤ k；每一步用 r-l+1 更新答案。O(n) 时间、O(1) 空间。
2. 正确性来自单调性：元素非负 ⇒ 固定 r 时 sum(l..r) 随 l 增大单调不增，所以左指针只需单向移动，收缩之后不用回头，r 也不用退。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 一个 N×N 的 0/1 网格，N=2000（共 400 万格），0 表示可通行，1 表示障碍，允许上下左右四方向移动，每走一格算 1 步。要求从 (0,0) 走到 (N-1,N-1)，给出最短步数，不可达返回 -1。内存上限 256MB。请说明你选 BFS 还是 DFS、队列和 visited 怎么设计、以及 visited 具体在什么时刻打标记。
• 社交关系图共 10^9 个用户，平均出度 200，边存放在分布式 KV 上（一次邻居查询约 5ms），单机可用内存 64GB。现在要找出指定用户 A 的 3 度以内（含 3 度）的全部用户 ID。你选 BFS 还是 DFS？写出你的遍历控制逻辑，估算 frontier（当前层待扩展集合）的最大规模，并说明用什么结构做去重。
• 你接手一个权限可达性服务：授权图约 500 万节点、2000 万条有向边（用户→角色→权限组→资源），业务上允许成环。线上要回答『用户 u 能否到达资源 r』，峰值 10 万 QPS、P99 要求 20ms。上一版实现是每次请求从 u 出发做一次 DFS，线上大面积超时并偶发栈溢出。请给出你的方案、演进路径和取舍。
• 给你一个 1000×1000 的 0/1 网格（1 是陆地，0 是水），上下左右相邻的陆地属于同一个岛，要求返回岛屿数量。A 同学用递归 DFS 做 flood fill，样例全过，但把规模放大到接近满屏陆地时程序崩溃。请说明崩溃的原因，写出你会怎么改；并说明同一份数据用 BFS 写时，队列规模的最坏情况是什么量级。
• 有向图有 4 个节点 s、a、b、t，边和权值是：s→a = 1，s→b = 2，b→a = -2，a→t = 3，b→t = 10。用朴素 Dijkstra（每次从未确定的节点里取 dist 最小的那个标记为已确定，之后不再更新它的 dist）从 s 求到 t 的最短路。请说出它算出的 dist[t] 是多少、正确答案是多少、差在哪一步上，然后说明什么样的图 Dijkstra 才是安全的。
• 一个城市路网约 10^8 个节点、2.5×10^8 条边，边权是通行时间（非负，但按早晚高峰每 5 分钟整体更新一次）。要支持单点到单点最短路查询、峰值 10^4 QPS、P99 延迟 < 50ms。朴素 Dijkstra 单次查询要扫描大量节点。你怎么选算法与架构？说清预处理成本、查询延迟、以及权重频繁变化带来的矛盾怎么权衡。