560.和为k的子数组-北京尧图网络

一、题目描述给你一个整数数组nums和一个整数k请你统计并返回该数组中和为k的子数组的个数。子数组是数组中元素的连续非空序列。示例 1输入nums [1,1,1], k 2 输出2示例 2输入nums [1,2,3], k 3 输出2提示1≤nums.length≤2×1041 \le nums.length \le 2 \times 10^41≤nums.length≤2×104−1000≤nums[i]≤1000-1000 \le nums[i] \le 1000−1000≤nums[i]≤1000−107≤k≤107-10^7 \le k \le 10^7−107≤k≤107⚠️ 重点数组包含负数不能用滑动窗口双指针二、暴力解法分析超时最容易想到的思路枚举子数组起点和终点累加区间和判断是否等于k。两层循环时间复杂度O(n2)O(n^2)O(n2)。当 n 达到 2e4 时运算量高达 4e8一定会超时无法通过。三、前缀和核心思想前缀和pre[i]数组从下标 0 加到下标 i 的总和。区间[j1,i][j1, i][j1,i]的和公式sumpre[i]−pre[j]sum pre[i] - pre[j]sumpre[i]−pre[j]题目要求区间和等于 kpre[i]−pre[j]kpre[i] - pre[j] kpre[i]−pre[j]k变形得到pre[j]pre[i]−kpre[j] pre[i] - kpre[j]pre[i]−k含义遍历到 i 的时候只要前面已经出现过前缀和等于pre[i] - k就对应一组合法连续子数组。四、前缀和哈希表优化思路哈希表作用记录每个前缀和出现的次数初始化mp[0] 1作用处理pre[i] k的场景也就是从数组开头到 i 的子数组满足条件。遍历流程当前前缀和加上当前元素查询pre - k是否存在哈希表存在则把对应次数加到答案将当前前缀和更新进哈希表计数1✅ 顺序不能颠倒先查询再存入哈希表避免重复使用当前位置五、C 代码实现#include unordered_map #include vector using namespace std; class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int mp; mp[0] 1; int pre 0, res 0; for (int x : nums) { pre x; if (mp.find(pre - k) ! mp.end()) { res mp[pre - k]; } mp[pre]; } return res; } };六、Python 代码实现from collections import defaultdict from typing import List class Solution: def subarraySum(self, nums: List[int], k: int) - int: cnt 0 pre 0 hashmap defaultdict(int) hashmap[0] 1 for x in nums: pre x if pre - k in hashmap: cnt hashmap[pre - k] hashmap[pre] 1 return cnt七、复杂度分析时间复杂度(O(n))(O(n))(O(n))数组一次遍历哈希表查询平均(O(1))(O(1))(O(1))空间复杂度(O(n))(O(n))(O(n))哈希表最多存储 n 个前缀和八、高频易错点总结数组存在负数前缀和不单调不能用双指针滑动窗口必须初始化mp[0] 1很多人漏掉这个条件导致样例不通操作顺序先查pre-k再更新哈希表不能反过来相同前缀和需要累加次数不是只记录是否存在

560.和为k的子数组

相关推荐

slub prefetch_freepointer

【C++开发】从裸指针到智能指针

【Linux网络】网络基础下篇：数据到底怎么从进程 A 到进程 B？从 MAC、IP、端口到 Socket 一次理清

更多资讯

从完美主义到无可挑剔：一套可复制的高质量行动法

ADS8688+STM32F407+RT-Thread高精度模拟量采集系统实战

代码质量量化落地：三层机制让“完美”不再只是口号

SXSSFWorkbook分页查询实现百万行Excel流式导出

对话模型记忆增强实战：claude-mem架构解析

AI编程中的规则约束：提升代码质量与工程效能

今日更新

基于YOLOv11的石油泄漏智能检测系统开发实践

AI行业变局：合规、Mod化与上下文管理的实战启示

计算机视觉与AI原生应用融合的技术实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？