数组中连续元素的总和，C

Question

假设我有一个由 n 个元素组成的数组。

 1 2 3 4 5 6 ... n

我需要找到一种方法来使用 C++ 提取此数组中连续元素的总和。像这样：

 1, 2, 3,...n, 1+2, 2+3, 3+4,...(n-1)+n, 1+2+3, 2+3+4,...(n-2)+(n-1)+n,...1+2+3...n

到目前为止，我发现我需要通过在每次运行时求和一定数量的元素来遍历这个数组。我不确定是否可以实现我上面解释的算法。可能有更好的解决方案，但这是我能想到的最好的解决方案。

原文由 harbinger 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

让我们检查包含 4 个元素的案例：

 {1,3,4,5, // from original array
 4,7,9, // sum of 2 consecutive elements
 8,12, // sum of 3
 13} // sum of 4

如您所见，N sum 数组的每个部分的大小都比原始数组小 (N-1)。所以你需要大小的目标数组： N + (N-1) + (N-2) + … 1 - 这是 N*(1+N)/2

 int* createSumArray(int* arr, int size)
{
   int ti = 0; // target index
   int* ta = new int[size*(size+1)/2];
   for (int s = 1; s <= size; ++s) // how many elements to sum
   {
      for (int si = 0; si < size + 1 - s; ++si)
      {
          ta[ti] = 0;
          for (int i = si; i < si + s; ++i)
            ta[ti] += arr[i];
          ++ti;
      }
   }
   return ta;
}

见 ideone 上的测试

原文由 PiotrNycz 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

您可以使用 std::transform 来执行此操作：

 std::transform(
    v.begin(), v.end()-1,
    v.begin()+1,
    std::ostream_iterator<int>(std::cout, "\n"),
    std::plus<int>()
);

当然，您不必使用 ostream_iterator 作为输出，也可以使用另一个容器迭代器，或者 std::back_inserter 用于容器或任何其他 OutputIterator

参考

http://en.cppreference.com/w/cpp/algorithm/transform

http://en.cppreference.com/w/cpp/utility/functional/plus

http://en.cppreference.com/w/cpp/container/vector

编辑：

 std::vector<int> v(100), t;
//this just populates v with 1,2,3...100
std::iota(v.begin(), v.end(), 1);

std::transform(
    v.begin(), v.end()-1, v.begin()+1,
    std::back_inserter(t),
    std::plus<int>()
);

std::transform(
    t.begin(), t.end()-1, v.begin()+2,
    std::ostream_iterator<int>(std::cout, "\n"),
    std::plus<int>()
);

原文由 111111 发布，翻译遵循 CC BY-SA 3.0 许可协议