站长之家查询工具,哈尔滨 网站开发,着力规范网站集约化建设,深圳展台制作公司题目描述
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1#xff1a;
输入#xff1a;nums [1,1,1], k 2
输出#xff1a;2示例 2#xff1a;
输入#xff1a;nums [1,2,3], k 3
输出#xff1a;2…题目描述
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1
输入nums [1,1,1], k 2
输出2示例 2
输入nums [1,2,3], k 3
输出2提示
1 nums.length 2 * 104-1000 nums[i] 1000-107 k 107
解答
class Solution {
public:int subarraySum(vectorint nums, int k) {// 前缀和[0, x]pfs[x] nums[0] nums[1] ... nums[x];// nums[x] pfs[x] - pfs[x-1]// nums的第i到j项和为// nums[i] nums[i1] ....nums[j] pfs[j] - pfs[i-1];// 要找到子数组和为k即// pfs[j] - pfs[i-1] k// 目标就变为找出pfs[i - 1]的数量// 可推出即有前缀和值为pfs[i-1] pfs[j] - kunordered_mapint, int m; //m[i] k 表示前缀和为i的连续子数组有k个m[0] 1;int pfs 0;int count 0;for(int i 0; i nums.size(); i){pfs nums[i]; // [0, i]范围元素的总和if(m.find(pfs - k) ! m.end()) //{count m[pfs - k];}m[pfs] 1;}return count;}
};
