C++前缀和算法的应用：统计得分小于K的子数组数目-摩杜云开发者社区

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

题目

一个数组的分数定义为数组之和乘以数组的长度。
比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。
给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数严格小于 k 的非空整数子数组数目。
子数组是数组中的一个连续元素序列。
示例 1：
输入：nums = [2,1,4,3,5], k = 10
输出：6
解释：
有 6 个子数组的分数小于 10 ：

[2] 分数为 2 * 1 = 2 。
[1] 分数为 1 * 1 = 1 。
[4] 分数为 4 * 1 = 4 。
[3] 分数为 3 * 1 = 3 。
[5] 分数为 5 * 1 = 5 。
[2,1] 分数为 (2 + 1) * 2 = 6 。
注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。
示例 2：
输入：nums = [1,1,1], k = 5
输出：5
解释：
除了 [1,1,1] 以外每个子数组分数都小于 5 。
[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。
所以总共有 5 个子数组得分小于 5 。
参数范围：
1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 1015

分析

题眼

num[i]是正数，这意味者单调递增。


推论一	如果r1<r2	则nums[left,r1)的积分比nums[left，r2)少，因为nums[r1,r2)的和大于0
推论二	如果r1<r2	如果nums[left,r1)不符合条件，则r2一定不符合条件
推论二	如果r1<r2	如果nums[left,r2)符合条件，则r1一定符合条件
令nums[left,r-1)的积分<k，nums[left,r)的积分大于等于k。则[left,left+1)…[left,r-1)都符合要求，共有：(r-1)-(left+1)+1=r-left-1个。

时间复杂度

两次循环，第一次循环枚举left，第二轮枚举r，两轮循环的时间复杂度都是O(n)。由于r不需要每次都置0，故总时间复杂度是O(n)。
nums[left,r-1)的积分<k ，所以nums[left+1,r-1)的积分也小于k，所以下一个left不会漏掉r。

代码

核心代码

class Solution {
 public:
 long long countSubarrays(vector& nums, long long k) {
 m_c = nums.size();
 vector vSums = { 0 };
 for (const auto& n: nums)
 {
 vSums.emplace_back(n + vSums.back());
 }
 int r = 0;
 long llRet = 0;
 //判断nums[left,r)是以k开头，第一个不小于 k 的积分
 for (int left = 0; left < m_c; left++)
 {
 while ((r <= m_c) && ((r - left) * (vSums[r] - vSums[left]) < k))
 {
 r++;
 }
 llRet += (r - 1) - left;
 }
 return llRet;
 }
 int m_c;
 };

测试用例

template
 void Assert(const vector& v1, const vector& v2)
 {
 if (v1.size() != v2.size())
 {
 assert(false);
 return;
 }
 for (int i = 0; i < v1.size(); i++)
 {
 assert(v1[i] == v2[i]);
 }
 }template
 void Assert(const T& t1, const T& t2)
 {
 assert(t1 == t2);
 }int main()
 {
 Solution slu;
 vector nums;
 long long k = 0;
 long long res;nums = { 2, 1, 4, 3, 5 };
k = 10;
res = slu.countSubarrays(nums, k);
Assert(6LL, res);
	
nums = {1,1,1 };
k = 5;
res = slu.countSubarrays(nums, k);
Assert(5LL, res);

nums = { 1,2,3,4,5,6 };
k = 10;
res = slu.countSubarrays(nums, k);
Assert(7LL, res);

nums = { 1,2,5,6,3,4 };
k = 11;
res = slu.countSubarrays(nums, k);
Assert(7LL, res);

nums = { 6,5,4,3,2,1 };
k = 12;
res = slu.countSubarrays(nums, k);
Assert(8LL, res);

//CConsole::Out(res);}

2022年11月旧代码

class Solution {
 public:
 long long countSubarrays(vector& nums, long long k) {
 vector sums(1);
 for (int i = 0; i < nums.size(); i++)
 {
 sums.push_back(nums[i] + sums[i]);
 }
 long long lRet = 0;
 for (int i = 0; i < nums.size(); i++)
 {
 lRet += Rec(sums, i, i, nums.size(), k) - i + 1;
 }
 return lRet;
 }
 int Rec(const vector& sums, const int& iBegin, const int& iMinIndex, const int& iMaxIndex, const long long& k)
 {
 if (iMaxIndex <= iMinIndex + 1)
 {
 if ((sums[iMinIndex + 1] - sums[iMinIndex]) < k)
 {
 return iMinIndex;
 }
 return iMinIndex - 1;
 }
 int iMid = (iMinIndex + iMaxIndex) / 2;
 if ((sums[iMid+1] - sums[iBegin])*(iMid-iBegin+1) < k)
 {
 return Rec(sums, iBegin, iMid, iMaxIndex, k);
 }
 return Rec(sums, iBegin, iMinIndex, iMid, k);
 }};

2023年7月旧代码

class Solution {
 public:
 long long countSubarrays(vector& nums, long long k) {
 vector vSum(1);
 for (const auto& n : nums)
 {
 vSum.emplace_back(n + vSum.back());
 }
 long long iRet = 0;
 for (int i = 0; i < nums.size(); i++)
 {
 int left = i, r = nums.size()+1;
 //[i,mid)分数小于k，求tmp的最大值 tmp为i表示空数组，tmp为nums.size()表示从i开始的整个数组
 while (r - left > 1)
 {
 const int mid = left + (r - left) / 2;
 const long long tmp = (mid - i) * (vSum[mid] - vSum[i]);
 if (tmp < k)
 {
 left = mid;
 }
 else
 {
 r = mid;
 }
 }
 iRet += left - i;
 }
 return iRet;
 }
 };

鄙人想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
墨家名称的来源：有所得以墨记之。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境：

VS2022 C++17

C++前缀和算法的应用：统计得分小于K的子数组数目_算法