c++ - C ++ 11查找总和>阈值的向量的最短前缀的方法

Question

如果我有一个vector<int>，那么用 sum > threshold 找到最短前缀的简洁 C++11 方法是什么？

Answer 1

int sum=0,threshold=10;
vector<int> vi = {4, 8, 11, 7};
auto sprefix = std::find_if(begin(v), end(v), [&](int elem){sum+=elem;return (sum>threshold);});

Answer 2

template <class Iter>
Iter find_prefix(Iter first, Iter last,
    typename std::iterator_traits<Iter>::value_type threshold) {
    Iter tmp = first;
    while (tmp != last) {
        if (threshold <= *tmp)
            return ++tmp;
        else
            threshold -= *tmp++;
    }
return first;
}

这适用于任何算术类型和由前向迭代器表示的任何值序列，而不仅仅是由 a 管理的序列vector。

Answer 3

这个问题有 O(n) 时间复杂度，所以一个有效的方法是：

int rangeIndex(vector<int>arr, int threshold)
{
    int i,sum = 0;

    for(i=0;i<arr.size();i++)
    {
        sum+=arr[i];

        if(sum>threshold)
        {
           return i;
        }
    }

    return -1;
}

此函数返回标记总和大于阈值的最短前缀结束的索引。如果不存在这样的前缀，则该函数返回 -1。

Answer 4

我找到了使用mutable兰巴的借口！

int n = 0;
auto iter = std::find_if(v.begin(), v.end(), [=](int x) mutable
    {
        n += x;
        return n > threshold;
    });

Answer 5

int size = vect.size(), length = -1, sum = 0;
while(++length < size)
    if( (sum += vect[length]) > threshold) break;
if(length == size) length = -1; // the whole sum is below the threshold!

length是最后一个前缀元素的索引，其中包含length+1数字。