本文涉及的基础知识点
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; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
