面试题库 › 算法 / 大模型 › 统计和在 [min, max] 内的连续子数组

统计和在 [min, max] 内的连续子数组

难度 ★★★在 1 场真实面经中被问到 方向:算法 / 大模型考点:数组与字符串

哪些公司问过

旷视科技1

常见岗位:自动驾驶

答案要点

  1. 子数组和 = P[j] - P[i],转化为统计 P[i] 落在 [P[j]-max, P[j]-min] 的对数
  2. 列出所有子数组只能 O(n²),结果规模本身可能是 O(n²)
  3. 只计数可用归并排序双指针或离散化加树状数组,O(n log n)
  4. 元素非负时用滑动窗口:count(≤max) - count(≤min-1),O(n)
  5. 前缀和用 64 位类型防溢出,注意区间端点开闭

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题