面试题库 › 算法 / 大模型 › 和为 K 的子数组(前缀和加哈希表)

和为 K 的子数组(前缀和加哈希表)

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

哪些公司问过

腾讯1滴滴1快手1华为1百度1小红书1

常见岗位:人工智能、大模型算法、NLP / 语音、Go 后端、C++ / Qt 客户端

答案要点

  1. 暴力枚举起点终点,O(n²)
  2. 子数组和等于 pre[i] 减 pre[j-1],转化为找前缀和 pre[i]-k 的出现次数
  3. 哈希表记录各前缀和出现次数,先统计再加入当前前缀和
  4. 初始化哈希表 {0:1},处理从开头开始的子数组
  5. 时间 O(n),空间 O(n);有负数,不能用滑动窗口

易错点

面试官常见追问

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

相关面试题