560. Subarray Sum Equals K

题目描述：

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:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

题目翻译

给定整数数组和整数k，您需要找到总和等于k的连续子序列的总数。

示例1：

输入： nums = [1,1,1]，k = 2
输出： 2

注意：

1. 序列的长度在[1，20,000]范围内。
2. 数组中的数字范围是[-1000,1000]，整数k的范围是[-1e7,1e7]。

解题方案

标签： Array

思路：

• 解题的思路是用一个sum记录前i个数的和，若sum[i]-sum2[j]=k，则说明下标从j到i-1的数的和为k，用两层for循环的思路易求得本题的答案。时间复杂度为o(n^2)。
• 但有没有更好的思路呢？当然是有！有o(n)的思路！用hashmap！怎么用？举个例子：若已知nums=[1,2,-1,-1,1,5],k=1。若用sums表示前i个数的和，那么有sums=[1,3,2,1,2,7]。
• 在每次得到新计算出的sum时，判断hashmap中是否存在key为sum-k的键值对，存在即取出加入结果。
• 再判断hashmap中是否存在key为sum的键值对，存在则将其值+1，否则初始化值为1。
• 循环一共n次，则实现了o(n)的思路。

代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        int sum=0,count=0;
        map.put(0,1);
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            if(map.containsKey(sum-k))
                count+=map.get(sum-k);
            if(map.containsKey(sum))
                map.put(sum,map.get(sum)+1);
            else
                map.put(sum,1);
        } 
        return count;
    }
}

参考资料

http://blog.csdn.net/marlonlyh/article/details/75675704