560-subarray-sum-equals-k

Try it on leetcode

Description

Solution(Python)

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        return self.hashingCumulativeSumFrequecny(nums, k)

    """
    Time Complexity: O(n^3)
    Space Complexity: O(1)
    """

    def bruteforce(self, nums: List[int], k: int) -> int:
        cnt = 0

        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if sum(nums[i: j + 1]) == k:
                    cnt += 1

        return cnt

    """
    Time Complexity: O(n^2)
    Space Complexity: O(n)
    """

    def CumulativeSum(self, nums: List[int], k: int) -> int:
        cnt = 0
        n = len(nums)
        CumSum = [0] * (n + 1)
        CumSum[0] = 0
        for i in range(1, n + 1):
            CumSum[i] = CumSum[i - 1] + nums[i - 1]

        for i in range(n):
            for j in range(i + 1, len(nums) + 1):
                if CumSum[j] - CumSum[i] == k:
                    cnt += 1
        return cnt

    """
    Time Complexity: O(n^2)
    Space Complexity: O(1)
    """

    def ConsecutiveSumOnthefly(self, nums: List[int], k: int) -> int:
        n = len(nums)
        cnt = 0

        for i in range(n):
            curSum = 0
            for j in range(i, n):
                curSum += nums[j]
                if curSum == k:
                    cnt += 1

        return cnt

    """
    Time Complexity: O(n)
    Space Complexity: O(n) 
    """

    def hashingCumulativeSumFrequecny(self, nums: List[int], k: int) -> int:
        n = len(nums)

        CumSum = 0
        CumSumFreq = defaultdict(lambda: 0)
        CumSumFreq[0] = 1  # by default sum with 0 is always going to  be there
        cnt = 0

        for i in range(n):
            CumSum += nums[i]
            if CumSum - k in CumSumFreq:
                cnt += CumSumFreq[CumSum - k]
            CumSumFreq[CumSum] += 1

        return cnt