java - Java 8 负子数组

Question

我正在 hackerrank.com 上通过 java 解决一些任务。任务是给出负子数组的数量。在输入上:第一行包含一个整数 n。下一行将包含 n 个空格分隔的整数。在输出上:打印负子数组的数量。

如果子数组中所有整数的总和为负，则该子数组为“负”。

(任务链接:https://www.hackerrank.com/challenges/java-1d-array-easy)

我正在尝试使用 Java 8 功能来解决此任务。我已经编写了通过所有测试并解决此任务的代码。但是，我想知道是否可以重构此代码以仅使用一个流操作。换句话说，我想知道如何写:

long result = Arrays.asList(....)
    ...
    .filter(sum -> sum < 0)
    .count();

我的解决方案:

public class Solution01 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        String s = sc.nextLine();
        sc.close();

        List<Integer> nums = Arrays.asList(s.split(" ")).stream()
                .map(Integer::parseInt)
                .collect(Collectors.toList());

        long result = getAllSubarrays(nums)
            .map(num -> mySum(num))
            .filter(sum -> sum < 0)
            .count();

        System.out.println(result);
    }

    public static Stream<List<Integer>> getAllSubarrays(List<Integer> array){
        List<List<Integer>> nums = new ArrayList<>();
        List<Integer> num;

        for(int i = 0; i < array.size(); i++){
            for(int j = i; j < array.size(); j++){
                num = new ArrayList<>();
                for(int k = i; k <= j; k++){
                    num.add(array.get(k));
                }
                nums.add(num);
            }
        }

        return nums.stream();
    }

    public static Integer mySum(List<Integer> nums){
        int sum = 0;
        for(int i = 0; i < nums.size(); i++)
            sum += nums.get(i);

        return sum;
    }
} 

PS。我没有使用第一行输入:)

Answer 1

我要声明以下简单的二次算法(比这更快，有人吗？)实际上是一个 Java 8 解决方案。在我看来，它比 this solution 更具表现力。 。它也快得多(通过基本测试)。当然，为了比较速度，我应该做一些JMH基准测试。对于 10_000-int 数组，它的运行速度通常比我计算机上提到的替代方案快两个数量级。

public class NumNegSubarrays {
    public static long get(int[] a) {
        long global = 0;
        for (int i = 0; i < a.length; i++) {
            long sum = 0, negs = 0;
            for (int j = i; j < a.length; j++) {
                sum += a[j];
                if (sum < 0)
                    negs += 1;
//                System.out.println("num of negative subarrays start-end: [" + i + ", " + j +"] = " + negs);
            }
            global += negs;
        }
        return global;
    }
    public static long finallyGet(int[] a) {
        List<Integer> nums = IntStream.of(a).boxed().collect(Collectors.toList());
        return IntStream.range(0, nums.size())
                .flatMap(from -> IntStream.range(from + 1, nums.size() + 1)
                        .map(to -> nums.subList(from, to).stream()
                                .mapToInt(i -> i)
                                .sum()))
                .filter(sum -> sum < 0)
                .count();
    }
    public static void main(String[] args) {
        int[] a = getSomeArray(10_00);
        long t1 = System.currentTimeMillis();
        System.out.println("Java: " + get(a));
        System.out.println("time: " + (System.currentTimeMillis() - t1) + " ms");
        t1 = System.currentTimeMillis();
        System.out.println("Java 8?: " + finallyGet(a));
        System.out.println("time: " + (System.currentTimeMillis() - t1) + " ms");
    }

    private static int[] getSomeArray(int n) {
        Random r = new Random();
        int[] a = new int[n];
        for (int i = 0; i < n; i ++)
            a[i] = r.nextInt(20) * (r.nextBoolean() ? 1 : -1);
        return a;
    }
}

示例运行:

Java: 118824
time: 6 ms
Java 8?: 118824
time: 362 ms

(答案相符!)