北京 成品网站,抚州市建设局网站,免费商用的cms,动易网站开发由于题目要求子数组必须连续#xff0c;也就是需要一个和为K的区间#xff0c;可以利用前缀和预处理后#xff0c;枚举找到这些区间段[l,r]#xff0c;使之满足s[r] - s[l] k。
不理解前缀和的可以先看这里。 class Solution {
public:int subarraySum(vectorint…由于题目要求子数组必须连续也就是需要一个和为K的区间可以利用前缀和预处理后枚举找到这些区间段[l,r]使之满足s[r] - s[l] k。
不理解前缀和的可以先看这里。 class Solution {
public:int subarraySum(vectorint nums, int k) {int s[nums.size() 1];memset(s, 0, sizeof s);// 存储前缀和定义从1开始for(int i 1;i nums.size();i ) s[i] nums[i - 1] s[i - 1];unordered_mapint, int mp; // 哈希表存下已经出现过的前缀和int cnt 0;// 确保s[i] k时能统计这单个s[i]为1个子数组s[i] - k 0mp[0] 1;for(int i 1;i nums.size();i ){//前面已经出现过的s[i] - k的个数正是和为 k 的子数组的个数//因为s[i]后 - (s[i] - k)前 kcnt mp[s[i] - k];mp[s[i]] ;}return cnt;}
};
