Subarray Sum K

Question

• GeeksforGeeks: Find subarray with given sum - GeeksforGeeks
• leetcode325

Problem Statement

Given an nonnegative integer array, find a subarray where the sum of numbers is k. Your code should return the index of the first number and the index of the last number.

Example

Given [1, 4, 20, 3, 10, 5], sum k = 33, return [2, 4].

题解1 - 哈希表

题 Zero Sum Subarray 的升级版，这道题求子串和为 K 的索引。首先我们可以考虑使用时间复杂度相对较低的哈希表解决。前一道题的核心约束条件为 $$f(i_1) - f(i_2) = 0$$，这道题则变为 $$f(i_1) - f(i_2) = k$$, 那么相应的 index 则为 $$[i_1 + 1, i_2]$$.

• reference
• visualization

class Solution(object):
    def maxSubArrayLen(self, nums, k):

        result, acc = 0, 0
        dic = {0: -1}

        for i in xrange(len(nums)):
            acc += nums[i]
            if acc not in dic:
                dic[acc] = i
            if acc - k in dic:
                result = max(result, i - dic[acc-k])

        return result
sol=Solution()
nums=[1, 4, 20, 3, 10, 5]
k=33
sol.maxSubArrayLen(nums,k)

class Solution:
    """
    @param nums: A list of integers
    @return: A list of integers includes the index of the first number 
                                      and the index of the last number
    """
    def subarraySum(self, A, k):
        hs = {0:-1}
        sum = 0
        for i in range(len(A)):
            # if A[i] == 0:
            #     return [i, i]
            sum += A[i]
            if sum-k in hs:
                return [hs[sum-k] + 1, i]
            hs[sum] = i
        return

sol=Solution()
A=[1, 4, 20, 3, 10, 5]
k=33
sol.subarraySum(A,k)