一个Leetcode问题“974.K可除子数组和”的时间复杂度分析

Question

我想出了一个解决这个问题的算法。然而，我不敢肯定这个解决方案的时间复杂性到底是什么。是O(n^3)还是O(n^2)，我想知道给定函数subarraysdivbyk的时间复杂度是多少？请帮忙

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

Answer 1

对于i的某些值，您将尝试j的所有值，从i到n。对于每个J，您将计算J-I元素的总和。为此，您需要O(0+1+...+(n-i))=O((n-i)^2)操作。因此，对于i的所有可能值，您需要O(n^2+(n-1)^2+...+2^2+1^2)=O(n^3)操作。回答:O(N^3)。