【滑动窗口】【二分查找】C++算法：和至少为 K 的最短子数组

template<class T = long long,bool bAsc= true >
class COrderValueIndexVector
{
public:
  COrderValueIndexVector(const vector<T>& vValue):m_vValue(vValue)
  {
  }
  void AddIndex(int index)
  {
    if (bAsc)
    {
      Add<std::less_equal<T>>(index);
    }
    else
    {
      assert(false);
    }
  } 
  //升序：最后一个小于等于的索引 
  int PreUpperBoundIndex(T value)
  {
    const int inx = std::upper_bound(m_vOrderValue.begin(), m_vOrderValue.end(), value) - m_vOrderValue.begin();
    if (inx > 0)
    {
      return m_vInx[inx - 1];
    }
    return -1;
  }
protected:  
  template<class _PR>
  void Add(int index)
  {
    //nums[l,r]的和为vPreSum[r+1]-vPreSum[l] >= k =>vPreSum[r+1] - k >= vPreSum[l]
    while (m_vOrderValue.size() && _PR()(m_vValue[index], m_vOrderValue.back()))
    {
      m_vInx.pop_back();
      m_vOrderValue.pop_back();
    }
    m_vInx.emplace_back(index);
    m_vOrderValue.emplace_back(m_vValue[index]);
  }
  vector<int> m_vInx;
  vector<T> m_vOrderValue;
  const vector<T>& m_vValue;
};
class Solution {
public:
  int shortestSubarray(vector<int>& nums, int k) {
    vector<long long> vPreSum = { 0 };
    for (const auto& n : nums)
    {
      vPreSum.emplace_back(n + vPreSum.back());
    }
    COrderValueIndexVector ov(vPreSum);
    int iRet = INT_MAX;
    for (int r = 0; r < nums.size(); r++)
    {
      //nums[l,r]的和为vPreSum[r+1]-vPreSum[l] >= k =>vPreSum[r+1] - k >= vPreSum[l]
      ov.AddIndex(r);
      const int left = ov.PreUpperBoundIndex(vPreSum[r + 1] - k);
      if (left >= 0 )
      {
        iRet = min(iRet, r - left + 1);
      }     
    }
    return (INT_MAX == iRet) ? -1 : iRet;
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<int> nums;
  int k;
  {
    Solution sln;
    nums = { 1 }, k = 1;
    auto res = sln.shortestSubarray(nums, k);
    Assert(1, res);
  }
  {
    Solution sln;
    nums = { 1,2 }, k = 4;
    auto res = sln.shortestSubarray(nums, k);
    Assert(-1, res);
  }
  {
    Solution sln;
    nums = { 2,-1,2 }, k = 3;
    auto res = sln.shortestSubarray(nums, k);
    Assert(3, res);
  }
//CConsole::Out(res);
}