了解 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]（returns 错误答案：["-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

你能尝试在检查差异时使用绝对值吗:

Math.abs(nums[i]) - Math.abs(nums[i-1])

我想这在负数的情况下看起来像是一个问题。

Answer 2

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

基本上，您的程序之间的区别在于您使用的是测试：

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

左边当然是合法的整数。右边的值也是一个合法的整数，因为你只是远离最小值。因此，不会溢出，并且比较会return false，这很好。

了解 Java 中的溢出问题

Understanding an overflow issue in Java

java

integer-overflow