I am doing this exercise

Thank you

CodePudding user response：

The problem with your algorithm is that it runs in quadratic time (i.e. O(n**2) where n is the size of the input array) while it could run in linear time (i.e. O(n)). The point is that you recompute the sum of the right part many times. This is not efficient because you only need to compute it once. You can store the cumulative sum in another array not to recompute it later (and get the right sum in constant time). You can for example pre-compute it at the beginning or just iteratively when it is needed based on the previous computed sum (see dynamic programming). Note that you can compute the cumulative sum easily and efficiently with the Numpy function numpy.cumsum.

Actually, a simpler algorithm is to compute the cumulative sum from the left to the right and in the reverse order and store them in two different arrays. Then, you can easily find the answer by iterating over the two array in lockstep from 0 to n to check if the left part is equal to the right part (excluding the current item).

CodePudding user response：

Try this:

def pivotIndex(self, nums: List[int]) -> int:
    for index in range(0, len(nums)):
        if sum(nums[:index]) == sum(nums[index   1:]):
            return index
    return -1

Best I could get, not very fast though.