java - 可变性测试中的 NumberOfDiscIntersections 溢出

Question

在适应性测试中NumberOfDiscIntersections我得到了 100% 的性能和 87% 的正确性，其中一个测试失败了

overflow
arithmetic overflow tests
got -1 expected 2

鉴于我使用的是 64 位的 long，我看不出是什么原因造成的。即使我能让它达到 100% perf 100% 正确性，我想知道是否有更好的方法来做到这一点，而不是在 Java 中那么冗长。

编辑:想出了一个更好的方法来处理两个数组而不是一对类

// you can also use imports, for example:
 import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        int j = 0;
        Pair[] arr = new Pair[A.length * 2];
        for (int i = 0; i < A.length; i++) {
            Pair s = new Pair(i - A[i], true);
            arr[j] = s;
            j++;
            Pair e = new Pair(i + A[i], false);
            arr[j] = e;
            j++;
        }
        Arrays.sort(arr, new Pair(0, true));

        long numIntersect = 0;
        long currentCount = 0;
        for (Pair p: arr) {
            if (p.start) {
                numIntersect += currentCount;
                if (numIntersect > 10000000) {
                    return -1;
                }
                currentCount++;
            } else {
                currentCount--;
            }
        }

        return (int) numIntersect;
    }

    static private class Pair implements Comparator<Pair> {
        private long x;
        private boolean start;
        public Pair(long x, boolean start) {
            this.x = x;
            this.start = start;
        }

        public int compare(Pair p1, Pair p2) {
            if (p1.x < p2.x) {
                return -1;
            } else if (p1.x > p2.x) {
                return 1;
            } else {
                if (p1.start && p2.start == false) {
                    return -1;
                } else if (p1.start == false && p2.start) {
                    return 1;
                } else {
                    return 0;
                }
            }
        }
    }
}

Answer 1

看这一行:

Pair s = new Pair(i + A[i], true);

这等同于 Pair s = new Pair((long)(i + A[i]) , true);

由于i是整数，A[i]也是整数，所以这会导致溢出，因为A[i]中的值> 可以达到 Integer.MAX_VALUE，并且转换为 long 发生在添加操作完成之后。

修复:

Pair s = new Pair((long)i + (long)A[i], true);

注意:我已经提交了修正并获得了 100%

https://codility.com/demo/results/demoRRBY3Q-UXH/