Basic knowledge points involved in this article
C++ algorithm: principles, source code and test cases of prefix sum, prefix product, prefix XOR including course videos
Title
The fraction of an array is defined as the sum of the arrays times the length of the array.
For example, the fraction of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) * 5 = 75 .
Given a positive integer array nums and an integer k, please return the number of non-empty integer subarrays in nums that are strictly less than k.
A subarray is a contiguous sequence of elements in an array.
Example 1:
Input: nums = [2,1,4,3,5], k = 10
Output: 6
explain:
There are 6 subarrays with scores less than 10:
- [2] The fraction is 2 * 1 = 2 .
- [1] The fraction is 1 * 1 = 1 .
- [4] The fraction is 4 * 1 = 4 .
- [3] The fraction is 3 * 1 = 3 .
- [5] The fraction is 5 * 1 = 5 .
- The fraction [2,1] is (2 + 1) * 2 = 6 .
Note that the subarrays [1,4] and [4,3,5] do not meet the requirement because their scores are 10 and 36 respectively, but we require that the subarrays’ scores are strictly less than 10 .
Example 2:
Input: nums = [1,1,1], k = 5
Output: 5
explain:
Every subarray score except [1,1,1] is less than 5.
The fraction [1,1,1] is (1 + 1 + 1) * 3 = 9 , which is greater than 5 .
So there are a total of 5 subarrays with scores less than 5.
Parameter range:
1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 1015
Analysis
Question eye
num[i] is a positive number, which means it is monotonically increasing.
| Corollary 1 | If r1| The points of nums[left,r1) are less than nums[left,r2), because the sum of nums[r1,r2) is greater than 0 |
|
| Corollary 2 | If r1| If nums[left,r1) does not meet the conditions, then r2 must not meet the conditions |
|
| Corollary 2 | If r1| If nums[left,r2) meets the conditions, then r1 must meet the conditions |
|
Let the integral of nums[left,r-1) |
|
| |
Time complexity
Two loops, the first loop enumerates left, and the second loop enumerates r. The time complexity of both loops is O(n). Since r does not need to be set to 0 every time, the total time complexity is O(n).
The integral of nums[left,r-1)
Code
Core code
class Solution {
public:
long long countSubarrays(vector & amp; 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;
longllRet = 0;
//Judge that nums[left,r) starts with k, and the first integral is not less than k
for (int left = 0; left < m_c; left + + )
{
while ((r <= m_c) & amp; & amp; ((r - left) * (vSums[r] - vSums[left]) < k))
{
r + + ;
}
llRet + = (r – 1) – left;
}
return llRet;
}
int m_c;
};
Test cases
template
void Assert(const vector & amp; v1, const vector & amp; 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 slug;
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);
\t
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);
}
Old code in November 2022
class Solution {
public:
long long countSubarrays(vector & amp; 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 & amp; sums, const int & amp; iBegin, const int & amp; iMinIndex, const int & amp; iMaxIndex, const long long & amp; 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);
}
};
Old code in July 2023
class Solution {
public:
long long countSubarrays(vector & amp; 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) score is less than k, find the maximum value of tmp. tmp is i, which means an empty array, and tmp, nums.size(), means the entire array starting from 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;
}
};
Extended reading
Video course
Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771
how fast do you want
A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176
Related downloads
If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653
| What I want to say to everyone |
|---|
| It is a good wish to be happy when you hear the flaws. Discover problems and correct them early to save your boss money. |
| The origin of the Mohist name: everything is recorded in Mohism. |
| If the program is a one-stop process, then the algorithm is its key point |
Test environment
Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 development environment:
VS2022 C++ 17
