数组稳定索引Java算法的嵌套循环时间复杂度分析

嘿，我来帮你理清这个时间复杂度的问题～首先先确认你的代码逻辑：遍历数组的每个索引，计算该索引左侧所有元素的和与右侧所有元素的和，相等则输出这个索引。我们一步步拆解：

原代码的时间复杂度（并非O(n)） #

你之前的误区在于，误以为每次外层循环里的两个内层循环总长度是固定的2n，但实际上不是这样的——我们来算总操作次数：

• 外层循环执行n次（n是数组长度）
• 对于第num次外层循环：
  • 第一个内层循环从0跑到num-1，执行num次
  • 第二个内层循环从num+1跑到数组末尾，执行n - num - 1次
• 把所有内层循环的执行次数加起来：$\sum_{num=0}^{n-1} (num + (n - num - 1)) = \sum_{num=0}^{n-1} (n-1) = n*(n-1)$

这意味着总操作次数是O(n²)（忽略常数项后）。举个直观的例子：你的示例数组长度是8，总内层循环次数是87=56次，远大于你以为的82=16次，这就能看出差异了。

优化到O(n)的实现 #

如果想要把时间复杂度降到你期望的O(n)，可以利用总和推导的思路，避免重复计算左右和：

1. 先一次性计算数组的总和totalSum
2. 遍历数组时，维护一个leftSum变量，实时记录当前索引左侧的元素和
3. 右侧元素的和可以直接通过totalSum - leftSum - arr[num]计算（总和减去左边和，再减去当前元素，剩下的就是右侧所有元素的和）

优化后的代码如下：

int[] arr = {0, -3, 5, -4, -2, 3, 1, 0};
int totalSum = 0;
for (int num : arr) {
    totalSum += num;
}
int leftSum = 0;
for (int num = 0; num < arr.length; num++) {
    int sumRight = totalSum - leftSum - arr[num];
    if (leftSum == sumRight) {
        System.out.print(num + " ");
    }
    leftSum += arr[num];
}

这段代码的输出和你的原代码完全一致：0 3 7，但时间复杂度是实打实的O(n)——只需要两次线性遍历（一次算总和，一次找稳定索引），没有嵌套循环。

关于你的原代码输出验证 #

顺便提一句，你的原代码输出0 3 7是完全正确的：

• 索引0：左侧无元素（和为0），右侧元素和为-3+5-4-2+3+1+0=0，相等
• 索引3：左侧和为0-3+5=2，右侧和为-2+3+1+0=2，相等
• 索引7：左侧和为0-3+5-4-2+3+1=0，右侧无元素（和为0），相等

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