Java中运算顺序变更致数组前缀和结果异常的原因探究

问题背景 #

我正在解决LeetCode上的「Range Sum of Sorted Subarray Sums」问题，问题描述如下：

给定由n个正整数组成的数组nums，计算所有非空连续子数组的和，将这些和按非递减顺序排序后得到一个长度为n*(n+1)/2的新数组。返回新数组中从left到right（下标从1开始）的元素和，结果需取模10^9+7。

示例1：

• 输入：nums = [1,2,3,4], n = 4, left = 1, right = 5
• 输出：13
• 解释：所有子数组和为1,3,6,10,2,5,9,3,7,4，排序后为[1,2,3,3,4,5,6,7,9,10]，取前5项和为13。

正确代码 #

class Solution {
    
    public static final int MOD = 1000000007; 

    public int rangeSum(int[] nums, int n, int left, int right) {
        int m = (n * (n + 1)) / 2;
        int[] arr = new int[m];

        for(int start = 0, index = 0; start < n; ++start){
            arr[index++] = nums[start];
            for(int i = start + 1; i < n; ++i){
                int lastIndexValInArray = arr[index - 1];
                arr[index++] = (lastIndexValInArray + nums[i]);
            }
        }

        System.out.println(Arrays.toString(arr));

        Arrays.sort(arr);

        int result = 0;

        for(int i = left - 1; i < right; ++i){
            result += arr[i];
            result%=MOD;
        }

        return result;
    }
}

当输入为new int[]{1,2,3,4}时，输出的子数组和数组为[1, 3, 6, 10, 2, 5, 9, 3, 7, 4]，符合预期。

修改后的错误代码 #

private int rangeSum(int[] nums, int n, int left, int right) {
    int m = (n * (n + 1)) / 2;
    int[] arr = new int[m];

    for(int start = 0, index = 0; start < n; ++start){
        arr[index++] = nums[start];
        for(int i = start + 1; i < n; ++i){
            arr[index++] = ( arr[index - 1] + nums[i] ); // 直接使用arr[index - 1]计算
        }
    }

    System.out.println(Arrays.toString(arr));

    Arrays.sort(arr);

    int result = 0;

    for(int i = left - 1; i < right; ++i){
        result += arr[i];
        result%=MOD;
    }

    return result;
}

此时输入new int[]{1,2,3,4}得到错误的子数组和数组[1, 2, 3, 4, 2, 3, 4, 3, 4, 4]。

差异原因解析 #

问题出在同一行代码中index的自增时机与数组访问顺序冲突，具体拆解如下：

在错误代码的核心行：

arr[index++] = ( arr[index - 1] + nums[i] );

Java的运算规则是：先处理左侧的数组下标定位，再计算右侧的表达式值，最后完成赋值。但这里的index++是后置自增，会提前改变index的值，导致右侧访问的数组位置出错：

以start=0、i=1的场景为例：

1. 进入循环时index=1，左侧的arr[index++]会先记录当前index=1作为要赋值的下标，然后立即将index自增为2。
2. 计算右侧表达式时，index已经是2，所以arr[index-1]实际访问的是arr[1]——这个位置还未被赋值，是数组的默认初始值0。最终计算出0+2=2，赋值给arr[1]，这显然不是我们需要的1+2=3。

而正确代码中，用中间变量提前获取了目标值：

1. 进入循环时index=1，先执行int lastIndexValInArray = arr[index-1]，此时index未被修改，获取的是arr[0]=1（上一个已赋值的正确子数组和）。
2. 再执行arr[index++] = 1+2=3，index自增为2，arr[1]被正确赋值。

简单来说，错误代码的本质是：在同一行里，左侧的index++提前修改了index，导致右侧访问的不是我们期望的“上一个已赋值的数组元素”，而是一个未初始化的位置。

内容的提问来源于stack exchange，提问作者John Doe