Description

Given an array of integers and an integer k, you need to find the total number of **continuous subarrays **whose sum equals to k.

Solution

同向模板
T O(N^2)
S O(N)

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int[] sum = new int[nums.length + 1];
        sum[0] = 0;
        for (int i = 1; i <= nums.length; i++)
            sum[i] = sum[i - 1] + nums[i - 1];
        for (int start = 0; start < nums.length; start++) {
            for (int end = start + 1; end <= nums.length; end++) {
                if (sum[end] - sum[start] == k)
                    count++;
            }
        }
        return count;
    }
}

Hashmap
首先求出nums的前缀和数组 (两个前缀和数组相减即可获得任意subarray)
然后将前缀和数组扫一遍，每扫到一个位置就将答案加上前面(k-prefixSum)出现次数（出现次数可以用dict维护）
再将当前前缀和prefixSum在出现的次数+1

class Solution:
    """
    @param nums: a list of integer
    @param k: an integer
    @return: return an integer, denote the number of continuous subarrays whose sum equals to k
    """
    def subarraySumEqualsK(self, nums, k):
        # write your code here
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
        d, ans = {0 : 1}, 0   #合为0的可以有一个（array为空时）
        for i in range(len(nums)):
            if(d.get(nums[i] - k) != None):  #找到！
                ans += d[nums[i] - k]
            if(d.get(nums[i]) == None):    
                d[nums[i]] = 1
            else:
                d[nums[i]] += 1
        return ans