C++前缀和算法应用：和至少为 K 的最短子数组的原理、源码及测试用例

class Solution {
public:
int shortestSubarray(vector& nums, int k) {
m_c = nums.size();
m_vRet.assign(m_c, -1);
vector<pair<long long, int>> vSumIndex = { {0,-1} };
long long llSum = 0;
m_vRet.assign(m_c, INT_MAX);
for (int i = 0; i < m_c; i++)
{
llSum += nums[i];
//sum-sumold >=k ==> sum-k>=sumold ==>sumold <= sum-k
//由于sum和index都是升序，所以可以二分
auto it = std::upper_bound(vSumIndex.begin(), vSumIndex.end(), llSum - k, []( const long long ll,const pair<long, int>& pi)
{
return ll < pi.first;
});
if (vSumIndex.begin() != it)
{
m_vRet[i] = i - std::prev(it)->second;
}
while (vSumIndex.size() && (vSumIndex.back().first >= llSum))
{
vSumIndex.pop_back();
}
vSumIndex.emplace_back(llSum, i);
}
const int iRet = *std::min_element(m_vRet.begin(), m_vRet.end());
return (INT_MAX == iRet) ? -1 : iRet;
}
int m_c;
vector m_vRet;
};

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);
}
class Solution {
public:
int shortestSubarray(vector& nums, int k) {
m_c = nums.size();
m_vRet.assign(m_c, -1);
vector<pair<long long, int>> vSumIndex = { {0,-1} };
long long llSum = 0;
m_vRet.assign(m_c, INT_MAX);
for (int i = 0; i < m_c; i++)
{
llSum += nums[i];
//sum-sumold >=k ==> sum-k>=sumold ==>sumold <= sum-k
//由于sum和index都是升序，所以可以二分
auto it = std::upper_bound(vSumIndex.begin(), vSumIndex.end(), llSum - k, []( const long long ll,const pair<long, int>& pi)
{
return ll < pi.first;
});
if (vSumIndex.begin() != it)
{
m_vRet[i] = i - std::prev(it)->second;
}
while (vSumIndex.size() && (vSumIndex.back().first >= llSum))
{
vSumIndex.pop_back();
}
vSumIndex.emplace_back(llSum, i);
}
const int iRet = *std::min_element(m_vRet.begin(), m_vRet.end());
return (INT_MAX == iRet) ? -1 : iRet;
}
int m_c;
vector m_vRet;
};

template
bool Less(const std::pair<Class1, int>& p, Class1 iData)
{
return p.first < iData;
}
template
bool Greater(const std::pair<Class1, int>& p, Class1 iData)
{
return p.first > iData ;
}
class Solution {
public:
int shortestSubarray(vector& nums, int k) {
int iMinLen = INT_MAX;
std::vector<std::pair<long, int>> vQue;
vQue.emplace_back(0, -1);
long long llSum = 0;
for (int i = 0; i < nums.size(); i++)
{
llSum += nums[i];
int iLessEqualNum = std::lower_bound(vQue.begin(), vQue.end(), llSum - k + 1, Less) - vQue.begin();
if (iLessEqualNum > 0 )
{
iMinLen = min(iMinLen, i - vQue[iLessEqualNum - 1].second);
}
while (vQue.size() && (llSum <= vQue.back().first))
{
vQue.pop_back();
}
vQue.emplace_back(llSum, i);
}
return (INT_MAX == iMinLen) ? -1 : iMinLen;
}
};