Java中如何使用Stream实现字符串数组转数字排序后求前缀和总和

解法思路 #

你原来的Stream写法只是对排序后的元素做了一次全量求和，要得到前缀和累加的目标结果，有两种可行的实现方式：

• 思路1：完全对齐原始双重循环逻辑，先遍历计算每一步的前缀和，再对所有前缀和求和
• 思路2（性能更优）：排序后索引为i（从0开始计数）的元素，会在数组总长度 - i个前缀和中出现，直接给每个元素乘以对应出现次数再求和即可，无需额外存储前缀和数组

思路2代码实现（推荐） #

import java.util.concurrent.atomic.AtomicInteger;
import static java.util.Arrays.stream;

public class Test {
    public static void main(String[] args) {
        String[] strings = {"3", "1", "4", "3", "2"};
        int arrLen = strings.length;
        AtomicInteger index = new AtomicInteger(0);
        int result = stream(strings)
                .mapToInt(Integer::parseInt)
                .sorted()
                .map(num -> num * (arrLen - index.getAndIncrement()))
                .sum();
        System.out.println(result); // 输出32
    }
}

说明：这里用AtomicInteger记录当前遍历索引，是因为Java lambda表达式不允许引用外部非final的普通变量，用原子类存储可变索引是常规实现方案。

思路1代码实现（对齐原始逻辑） #

import static java.util.Arrays.stream;

public class Test {
    public static void main(String[] args) {
        String[] strings = {"3", "1", "4", "3", "2"};
        int[] sortedArr = stream(strings)
                .mapToInt(Integer::parseInt)
                .sorted()
                .toArray();
        // 用长度为1的数组存储前缀和变量，解决lambda不能引用可变普通变量的问题
        int[] prefixSum = {0};
        int result = stream(sortedArr)
                .map(num -> {
                    prefixSum[0] += num;
                    return prefixSum[0];
                })
                .sum();
        System.out.println(result); // 输出32
    }
}

内容的提问来源于stack exchange，提问作者shirohoo