数组所有连续子数组求和：现有解法超时，求更优方案

嘿，这个问题我之前也踩过坑！你的三重循环解法逻辑是对的，但O(n³)的时间复杂度在数组规模变大时肯定会超时——毕竟n=1000的话，就要执行10亿次操作，完全扛不住。咱们换个思路，直接把时间复杂度降到O(n)，效率提升不是一点点！

核心思路：计算每个元素的贡献值 #

与其枚举所有子数组再求和，不如反过来算每个元素在多少个连续子数组里出现，然后用「元素值 × 出现次数」得到这个元素对总和的总贡献，最后把所有元素的贡献加起来就行。

具体来说，对于数组中下标为i的元素arr[i]（下标从0开始）：

• 子数组的起始点可以是从0到i中的任意一个，共i+1种选择
• 子数组的结束点可以是从i到n-1中的任意一个，共n - i种选择
  所以这个元素总共会出现在(i+1) × (n - i)个子数组里，它的总贡献就是 arr[i] × (i+1) × (n - i)

用示例验证一下 #

比如你给的第一个示例{1,2,3}：

• 元素1（下标0）：贡献=1 × (0+1) × (3-0) = 1×1×3=3
• 元素2（下标1）：贡献=2 × (1+1) × (3-1) = 2×2×2=8
• 元素3（下标2）：贡献=3 × (2+1) × (3-2) =3×3×1=9
  总和3+8+9=20，完全符合示例输出。

再看{1,1,1}：

• 第一个1：1×1×3=3
• 第二个1：1×2×2=4
• 第三个1：1×3×1=3
  总和3+4+3=10，也和示例一致。

优化后的代码 #

long sum(int[] arr) {
    long total = 0;
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        // 注意强制转long，避免int溢出
        total += (long) arr[i] * (i + 1) * (n - i);
    }
    return total;
}

这里要注意把arr[i]先转成long，不然当数组元素和乘积比较大时，int类型会溢出，导致结果错误。

这个解法只需要一次遍历数组，时间复杂度O(n)，空间复杂度O(1)，就算处理百万级别的数组也能轻松搞定～

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