统计和在 [min, max] 内的连续子数组
哪些公司问过
旷视科技1
答案要点
- 子数组和 = P[j] - P[i],转化为统计 P[i] 落在 [P[j]-max, P[j]-min] 的对数
- 列出所有子数组只能 O(n²),结果规模本身可能是 O(n²)
- 只计数可用归并排序双指针或离散化加树状数组,O(n log n)
- 元素非负时用滑动窗口:count(≤max) - count(≤min-1),O(n)
- 前缀和用 64 位类型防溢出,注意区间端点开闭
易错点
- 有负数时仍用滑动窗口
- 前缀和用 32 位整数导致溢出
- 漏掉 P[0]=0,统计不到从开头开始的子数组
面试官常见追问
- 归并排序为什么能统计?
- 有负数时为什么不能用滑动窗口?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场