分析Leetcode 974和可被K整除的子数组给定解法的时间复杂度

复杂度结论 #

你提供的subarraysDivByK函数时间复杂度为O(n³)，推导过程如下：

• 第一层i循环共执行n次，遍历所有子数组的左边界
• 第二层j循环对于每个i，遍历从i到n-1的所有右边界，两层循环总执行次数为 $\frac{n(n+1)}{2}$，属于O(n²) 量级
• 每次内层循环都会调用findSum函数，该函数需要遍历[i,j]区间内的所有元素求和，单次执行次数为j-i+1，平均每次调用需要遍历O(n) 个元素

三层执行次数叠加后，总操作数规模为 $\frac{n(n+1)(n+2)}{6}$，对应时间复杂度为O(n³)。

优化建议 #

如果想要将时间复杂度降到O(n²)，可以在内层循环中维护当前窗口的累加和，避免每次重复遍历区间求和，优化后代码如下：

public int subarraysDivByK(int[] A, int K) 
{
    int n = A.length;
    int count = 0;
    for(int i=0;i<n;i++)
    {
        int sumWindow = 0;
        for(int j=i;j<n;j++)
        {
            sumWindow += A[j];
            if(sumWindow % K == 0)
            {
                count++;
            }
        }
    }
    return count;
}

如果要满足Leetcode 974的时间限制（输入规模最高可达$310^4$），还可以进一步使用前缀和同余计数的方法将复杂度降到O(n)*。

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