如何使用Java Streams或输入阶段处理实现数组的迭代累加（低复杂度方案）

Great question! 要生成前缀和数组，核心是处理有状态的累加——每个元素的结果依赖前一个的累加值，而普通Stream操作是无状态的，所以我们需要用一些小技巧来保留状态，同时保证O(n)的时间复杂度（这是前缀和问题的最优复杂度，毕竟每个元素必须遍历一次）。

下面是几种实用的方案，按性能和简洁性排序：

1. 轻量可变累加器（最优性能） #

用一个int数组作为累加容器（因为数组是引用类型，能在lambda表达式中修改内部值），串行流下完全安全，且没有额外的原子操作开销：

int[] original = {1, 1, 1, 2, 3};
int[] accumulator = {0}; // 用数组存累加值，避免lambda的不可变限制

int[] prefixSum = Arrays.stream(original)
                        .map(num -> accumulator[0] += num)
                        .toArray();

// 输出结果：[1, 2, 3, 5, 8]

说明： #

• 时间复杂度O(n)，每个元素仅处理一次；空间复杂度O(n)（结果数组的空间是必须的，额外仅占用一个int数组的空间）。
• 必须使用串行流：如果开启并行流，多个线程会同时修改accumulator[0]，导致结果错误。如果不确定流的默认模式，可显式添加.sequential()确保串行执行。

2. AtomicInteger累加器（线程安全但略逊性能） #

如果需要兼顾线程安全（比如偶尔可能用并行流，但其实前缀和不适合并行），可以用AtomicInteger作为累加器：

int[] original = {1, 1, 1, 2, 3};
AtomicInteger sum = new AtomicInteger(0);

int[] prefixSum = Arrays.stream(original)
                        .map(sum::addAndGet)
                        .toArray();

说明： #

• 原理和第一种一致，但addAndGet是原子操作，会带来微小的性能开销，所以串行场景下第一种更优。
• 并行流下虽然不会出错，但前缀和的计算依赖前序结果，并行执行反而会因为线程同步降低效率，所以不推荐用并行流处理这类问题。

3. 纯函数式实现（无可变状态） #

如果追求纯函数式风格，不使用可变变量，可以用Stream.iterate来生成状态序列：

int[] original = {1, 1, 1, 2, 3};
List<Integer> prefixList = Stream.iterate(
        new int[]{0, 0}, // 初始状态：[当前索引, 当前累加和]
        state -> {
            int nextIdx = state[0] + 1;
            int nextSum = state[1] + original[nextIdx];
            return new int[]{nextIdx, nextSum};
        }
)
.limit(original.length) // 生成和原数组长度一致的元素
.map(state -> state[1]) // 提取累加和
.collect(Collectors.toList());

// 转成int数组
int[] prefixSum = prefixList.stream().mapToInt(Integer::intValue).toArray();

说明： #

• 完全无可变状态，符合函数式编程理念，但每次迭代都会创建新的int数组，性能略低于前两种方案，复杂度仍然是O(n)。
• 适合对代码风格有严格要求的场景，但不是性能最优的选择。

总结 #

如果追求最优性能和低复杂度，优先选择第一种用int数组作为累加器的方案，它在串行流下实现了O(n)时间和最小的额外空间开销，代码也足够简洁。

内容的提问来源于stack exchange，提问作者Maulik Pipaliya Joyy