子数组和小于C的个数

条件：数组 x 中数以及C为整数，假定结果不爆 int
1、都为正整数
滑动窗口，从[lo=0, hi=0]开始维护即可，时间：O(n)
2、任意整数
思路：维护一个前缀和 prefix 以及有序集合 set，遍历到 x[i] 时，更新 prefix，同时将 prefix加入 set，此时，我们只要在 set 中找 最小的>=prefix-(C-1) 的前缀和 p 即可（剩下的必然尽可能接近C），用 prefix-p 更新答案即可。时间：O(nlogn)

int maxSubSumLessC(vector<int>& x, int C) {
    int ans = 0;
    int prefix = 0;
    set<int> st;
    st.insert(0); //
    for(auto num : x) {
        prefix += num;
        st.insert(prefix);
        auto p = lower_bound(st.begin(), st.end(), prefix-(C-1));    
        if(p != st.end()) ans = max(ans, prefix-*p);
    }
    return ans;
}