使用java 8查找连续子列表的负和

Question

我正在尝试优化以下代码:

private final static class SubarrayProcessorNegativeSumStrategy 
    implements SubarrayProcessorStrategy {
    @Override public Integer apply(Integer[] array) {
        final List<Integer> numbers = Arrays.asList(array);
        return (int) IntStream.range(0, numbers.size())
            .map(index -> findNegativeSums(numbers, index)).sum();
    } 
    private Integer findNegativeSums(final List<Integer> numbers, 
                                     final Integer startIndex) {
    final Integer numbersSize = numbers.size();
    if (startIndex < numbersSize) {
        return (int) IntStream.range(startIndex, numbers.size())
        .map(newIndex -> numbers.subList(startIndex, newIndex + 1)
        .stream().mapToInt(x -> x).sum())
        .filter(sum -> sum < 0).count();
    } else {
        return 0;
    }
}

我想避免迭代startIndex到newIndex + 1原始List的每个元素

numbers.subList(startIndex, newIndex + 1).stream().mapToInt(x -> x).sum()

你有什么建议我怎样才能做到这一点？或者如果您能提供任何改进以获得相同的结果？

谢谢

问候,

Answer 1

如果您想通过StreamAPI 实现它,则无需List绕过API.此外,如果执行单个flatMap流操作,«元素计数的总和»是所有元素的总数:

private final static class SubarrayProcessorNegativeSumStrategy
    implements SubarrayProcessorStrategy {
    @Override public Integer apply(Integer[] array) {
        return (int)IntStream.rangeClosed(0, array.length)
            .flatMap(index -> IntStream.range(0, index)
                .map(newIndex -> Arrays.stream(array,newIndex,index).mapToInt(x->x).sum())
                .filter(sum -> sum < 0))
            .count();
    }
}

这仍然具有嵌套迭代的相同时间复杂度.如果要优化执行时间,有状态操作更适合任务,这不是StreamAPI的一个好用例.使用普通循环是直截了当的:

private final static class SubarrayProcessorNegativeSumStrategy 
    implements SubarrayProcessorStrategy {
    @Override public Integer apply(Integer[] array) {
        int count=0;
        for(int index = 0; index < array.length; index++) {
            for(int newIndex = index, currSum = 0; newIndex < array.length; newIndex++) {
                currSum += array[newIndex];
                if(currSum < 0) count++;
            }
        }
        return count;
    }
}