java - 了解 Java 中的溢出问题

Question

Given a sorted integer array without duplicates, return the summary of its ranges for consecutive numbers.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

我提出了以下解决方案:

public List<String> summaryRanges(int[] nums) {
    if (nums == null){
        return null;
    }
    if (nums.length == 0){
        return new ArrayList<>();
    }
    if (nums.length == 1){
        List<String> arr = new ArrayList<>();
        arr.add(Integer.toString(nums[0]));
        return arr;
    }

    List<String> summary = new ArrayList<>();
    int n = nums.length;
    int begin = nums[0];
    int end;

    for (int i = 1; i < n; i++) {
        if (nums[i] - nums[i-1] > 1) {
            end = nums[i-1];
            if (begin == end){
                summary.add(Integer.toString(begin));

            }
            else{
                summary.add(Integer.toString(begin) + "->" + Integer.toString(end));
            }
            begin = nums[i];
        }
    }
    if (nums[n-1] - nums[n-2] > 1){
        summary.add(Integer.toString(nums[n-1]));
    }
    else{
        summary.add(Integer.toString(begin) + "->" +Integer.toString(nums[n-1]));
    }

    return summary;
}

此程序在以下示例中失败:[-2147483648, -2147483647, 2147483647](返回错误答案:["-2147483648->2147483647"])

我怀疑这是由于溢出问题造成的，但我无法弄清楚具体原因。相反，我发现的这个示例解决方案通过了这个测试用例:

public List<String> summaryRanges(int[] nums) {
    List<String> result = new ArrayList<String>();

    if(nums == null || nums.length==0)
        return result;

    if(nums.length==1){
        result.add(nums[0]+"");
    }

    int pre = nums[0]; // previous element   
    int first = pre; // first element of each range

    for(int i=1; i<nums.length; i++){
            if(nums[i]==pre+1){
                if(i==nums.length-1){
                    result.add(first+"->"+nums[i]);
                }
            }else{
                if(first == pre){
                    result.add(first+"");
                }else{
                    result.add(first + "->"+pre);   
                }

                if(i==nums.length-1){
                    result.add(nums[i]+"");
                }

                first = nums[i];
            }

            pre = nums[i];
    }

    return result;
}

为什么这个解决方案通过了这一测试，而不是我提出的测试？

Answer 1

是的，确实，问题是溢出。

您的程序之间的区别基本上在于您正在使用测试:

nums[i] - nums[i-1] > 1

而其他程序使用

nums[i]==pre+1

在纯数学世界中，将 y 与 x+1 进行比较以及将 y-x 与 1 进行比较应该没有区别，但在 32 位整数的世界里，有很大的区别。

当您看到数字 -Integer.MAX_VALUE 和 Integer.MAX_VALUE(即示例数组中的数字)时，您的比较结果为:

Integer.MAX_VALUE - -Integer.MAX_VALUE > 1

由于减号相互抵消，这意味着 2 * Integer.MAX_VALUE，它大于 int 可以容纳的大小，并且会发生溢出。结果是 -2 并且不大于 1。

以其他程序的方式，您会问是否

Integer.MAX_VALUE == - Integer.MAX_VALUE + 1

左边部分当然是一个合法的整数。右手边的值也是一个合法的整数，因为你只是远离最小值。因此，没有溢出，并且比较将返回 false，这很好。