Subarray Sum Equals K I've written a solution to the following leetcode problem:


  Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
  
  Example 1:
  Input: nums = [1,1,1], k = 2
  Output: 2
  
  Note:
  The length of the array is in range [1, 20,000].
  The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].


Solution:

class Solution:
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        T = ['inf' for _ in range(len(nums))]
        count = 0
        for i in range(len(nums)):
            for j in range(i,len(nums)):
                if j == i:
                    T[i] = nums[i]
                    if T[i] == k:
                        count +=1
                else:
                    currSum = T[j-1] + nums[j]
                    T[j] = currSum
                    if currSum == k:
                        count +=1
        return count


The solution passes 58/80 test cases, but for some reason, the solution is returning a Time Limit Exceeded exception on an input array with hundreds of elements. I implemented a dynamic programming solution using a 1d array to memoize previous sums so the algorithm should be efficient. Is there any way to optimize this?
These nested loops

    for i in range(len(nums)):
        for j in range(i,len(nums)):


undoubtedly make the time complexity quadratic. This is the reason for TLE. There is no point to optimize this code; you need to rethink the approach. I don't want to spell out the linear algorithm, and deprive you the fun of finding it. Hint: think of the sliding window.



A condition j == i inside the inner loop happens exactly once, and we perfectly know when. Lift it out:

    for i in range(len(nums)):
        T[i] = nums[i]
        if T[i] == k:
            count +=1
        for j in range(i + 1, len(nums)):
            currSum = T[j-1] + nums[j]
            T[j] = currSum
            if currSum == k:
                count +=1