560 Subarray Sum Equals K

Leetcode

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

对数组进行求和得到一个求和数组，第 i 个元素的值为原数组从 1 到第 i 个元素之和。求和后的数组两个下标元素之差为原数组的子数组的和（前不包后包），再算上求和数组单个元素的值（为原数组从 0 到该元素这个子数组的和）

最开始的做法，依次遍历所有下标组合，发现只超过 5% Java 代码的速度。。。时间复杂度 o(n²)

public int subarraySum(int[] nums, int k) {
    for(int i=1;i<nums.length;++i){
        nums[i]+=nums[i-1];
    }
    int count=0;
    for(int i=0;i<nums.length;++i){
        for(int j=i+1;j<nums.length;++j){
            if(nums[j]-nums[i]==k) count++;
        }
        if(nums[i]==k) count++;
    }
    return count;
}

可以使用 HashMap 来记录前面这个和出现多少次，实现时间复杂度 o(n)

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