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].
My code:
class Solution(object):
def subarraySum1(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
#O n^2 which is accepted, however for python~~~
if len(nums)==0:
return 0
count_all=0
for i in range(len(nums)):
tmp_count=nums[i]
if tmp_count==k:
count_all+=1
for j in range(i+1,len(nums)):
tmp_count+=nums[j]
if tmp_count==k:
count_all+=1
continue
return count_all
def subarraySum(self, nums, k):
if len(nums) < 1:
return 0
# sum frequency table
# maps sum -> number of occurences of that sum
# this is built up as we go, NOT precomputed
sft = {}
curr_sum = 0
occurences = 0
for num in nums:
# calculate current sum and check for equality
# if there is a match, we increment occurences counter
curr_sum += num
if curr_sum == k:
occurences += 1
# we are also interested in the number of times curr_sum-k
# appears in the sum frequency table
# add all of those occurences as well
#Check from some point to now point a subsequent sum,excellet idea with this
diff = curr_sum - k
if diff in sft:
occurences += sft[diff]
# finally, store the current sum in the sum frequency table
if curr_sum in sft:
sft[curr_sum] += 1
else:
sft[curr_sum] = 1
print(occurences)
return occurencesSolution: https://leetcode.com/problems/subarray-sum-equals-k/solution/