560 Subarray Sum Equals K

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

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].

老规矩，先来一个暴力破解的方法，遍历求累加和，判断是否为n，一看代码就能明白，如下：

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

上述方法其实也能accept，执行结果如下：可以看到耗时还是比较长的

执行耗时:112 ms,击败了27.18% 的Java用户 内存消耗:38.6 MB,击败了98.91% 的Java用户

方法二：

想到网上一种传统的解决这种问题的思路，利用一个累加和数组，其实思路比较简单，但是还不如暴力来得快呢

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

    }
    return count;
}

方法三：

利用一个map保存当前累加和的值，和对应的count，但是在求解时还需要注意，我并没有理解透彻。可以看下代码，然后手动推导 过程：

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

用map的查找功能来代替遍历数组(字符串)是一个常用的节省时间的方案，一旦需要频繁查找的时候，都可以往map上想一想。

结果是： 执行耗时:15 ms,击败了44.44% 的Java用户 内存消耗:38.4 MB,击败了98.91% 的Java用户