二分查找|前綴和|滑動窗口|2302:統計得分小于 K 的子數組數目

作者推薦

貪心算法LeetCode2071:你可以安排的最多任務數目

本文涉及的基礎知識點

二分查找算法合集

題目

一個數組的分數定義為數組之和乘以數組的長度。
比方說，[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 <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 10¹⁵

二分查找、前綴和

代碼

時間復雜度

O(nlogn)。枚舉子數組起點，時間復雜度O(n)；二分查找終點：時間復雜度O(logn)。

原理

尋找最后一個符合以下條件的vNumRight，故用左閉右開空間。vNumRight的取值范圍是[vNumLeft,m_c]，換成左閉右開空間是[vNumLeft,m_c+1)。nums[vNumLeft,vNumRight) 就是要判斷的子數組。

核心代碼

class Solution {
public:long long countSubarrays(vector<int>& nums, long long k) {m_c = nums.size();vector<long long> vPreSum = { 0 };for (const auto& n : nums){vPreSum.emplace_back(vPreSum.back() + n);}long long llRet = 0;for (int vNumLeft = 0; vNumLeft < m_c; vNumLeft++){//求最大的vNumRight，使得nums[vNumLeft,vNumRight)的得分小于k。左閉右開int left = vNumLeft, right = m_c + 1;while (right - left > 1){const auto mid = left + (right - left) / 2;if ((vPreSum[mid] - vPreSum[vNumLeft])*(mid-vNumLeft) < k){left = mid;}else{right = mid;}}llRet += left - vNumLeft;}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()
{
vector nums;
long long k,res;
{
Solution slu;
nums = { 2, 1, 4, 3, 5 }, k = 10;
auto res = slu.countSubarrays(nums, k);
Assert(6LL, res);
}
{
Solution slu;
nums = { 1,1,1 }, k =5;
auto res = slu.countSubarrays(nums, k);
Assert(5LL, res);
}
{
Solution slu;
nums = { 9,5,3,8,4,7,2,7,4,5,4,9,1,4,8,10,8,10,4,7 }, k = 4;
auto res = slu.countSubarrays(nums, k);
Assert(3LL, res);
}
//CConsole::Out(res);
}

滑動窗口

時間復雜度O(n)

由于是正整數，所以子數組起點相同，終點越大，積分越大。相同的left,right不斷增大。left增大，right不變或變大。left循環O(n)次,right也是。right總共循環了o(n)，每次都是接著上次的right開始，沒有重新開始。

代碼

class Solution {
public:long long countSubarrays(vector<int>& nums, long long k) {m_c = nums.size();long long llSum = 0;long long llRet = 0;for (int left = 0,right=0; left < m_c; left++){//子數組nums[left,right)符合要求，且right是當前left的最大值while ((right < m_c) && ((llSum+nums[right]) * (right+1 - left) < k)){llSum += nums[right++];}llRet += right - left;llSum -= nums[left];}	return llRet;}int m_c;
};

擴展閱讀

視頻課程

有效學習：明確的目標及時的反饋拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

我想對大家說的話
聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者操作系統：win10 開發環境：

VS2022 C++17

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/208808.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/208808.shtml
英文地址，請注明出處：http://en.pswp.cn/news/208808.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！