Java实现现有数组最大跨度重复值子数组长度计算时遇数组越界异常修复

异常触发根因 #

• 堆栈报出的Index 0 out of bounds for length 0问题，本质是数组初始化时序错误：方法启动时先将maxDifference设为0，紧接着用这个0值创建数组，得到一个长度为0的空数组。Java中数组实例化后长度固定不可修改，后续循环中即便maxDifference被更新为更大的值，已经创建的空数组长度不会同步变化。
• 当程序进入更新maxDifference的分支执行数组赋值时，长度为0的数组不存在下标为0的位置，直接触发越界异常，对应堆栈中workout.lis方法第15行的报错位置。

原有实现的逻辑缺陷 #

• 冗余计算：内层循环从j=0开始遍历，会无意义比对所有i==j的元素对，这类元素对的索引差永远为0，不会对结果产生有效贡献
• 长度计算偏差：两个相同元素的索引位置差为j-i时，夹在中间的子数组实际元素个数为j-i+1，直接用索引差作为数组长度会少算1个元素
• 逻辑错位：最终仅需要返回子数组长度，原有代码逐次给空数组赋值的操作没有实际价值，且因为数组创建时机过早，必然触发越界

具体修复步骤 #

1. 调整数组创建时序：遍历完所有元素对、确定最大索引差值后，再根据最终的长度值实例化数组，从根源上避免空数组赋值
2. 优化循环边界：将内层j的遍历起点设为i+1，跳过重复的无意义比对，降低无效循环量
3. 修正长度计算规则：最终返回的子数组长度为相同元素的最大索引差值加1，匹配实际包含的元素个数
4. 移除无意义的中间赋值：维护两个独立变量记录最大索引差、对应的相同元素值，等数组创建完成后再统一填充内容

修复后参考代码 #

public class workout {
    public static int lis(int[] A, int n){       
        int maxDiff = 0;
        int sameElementVal = 0; // 记录最大差值对应的相同元素值
        // 遍历所有元素对找相同值的最大索引差
        for (int i = 0; i < n; i++){
            // 内层从i+1开始遍历，避免重复比对
            for( int j = i + 1; j < n; j++ ){
                if( A[i] == A[j]){
                    int currentDiff = j - i;
                    if (currentDiff > maxDiff){
                        maxDiff = currentDiff;
                        sameElementVal = A[i];
                    }
                }
            }
        }
        // 拿到最大差值后再创建数组，此时数组长度完全匹配
        int targetLength = maxDiff + 1;
        int newList[] = new int[targetLength];
        // 数组创建完成后再执行填充操作
        for (int x = 0; x < targetLength; x++){
            newList[x] = sameElementVal;
        }
        return newList.length;
    }

    public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4, 4, 3, 2, 5 };
        int n = arr.length;
        System.out.println("Length of lis is " + lis( arr, n ) + "\n" );
    }
}

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