Subarray Sum Equals K

Posted on |

问题描述（难度中等）

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:

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

方法一：递归

可以拆解为多个子问题。通过递归的方式求解，时间复杂度O(N^2)，空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package P560;

class Solution {
    private int[] nums;
    public int subarraySum(int[] nums, int k) {
        this.nums=nums;
        return maxArraySum(nums.length-1,k);
    }
    public int maxArraySum(int i,int k){
        if (i==0) {
            return nums[0]==k?1:0;
        }
        return maxArraySum(i-1,k)+tempArraySum(i-1,k-nums[i])+(nums[i]==k?1:0);
    }
    public int tempArraySum(int i,int k){
        if (i==0) {
            return nums[0]==k?1:0;
        }
        return tempArraySum(i-1,k-nums[i])+(nums[i]==k?1:0);
    }
    public static void main(String[] args) {
        int[] nums={1,1,1};
        new Solution().subarraySum(nums,2);
    }
}

方法二：HashMap

通过map存储和出现的次数，key为[0,j]元素的和，value为和出现的次数。假设[i,j]为和为k的数组，那么sum(0,j)-k=sum(0,i)。时间复杂度O(N),空间复杂度O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package P560;


import java.util.HashMap;
import java.util.Map;

/**
 * 采用map记录 key为[0,j]的和 value为和出现的次数
 * [i,j]为和为k的位置 那么sum(0,j)-k=sum(0,i)
 * @autor yeqiaozhu.
 * @date 2019-10-30
 */
public class UsingMap {
    Map<Integer,Integer> counts=new HashMap<>();
    public int subarraySum(int[] nums, int k) {
        int sum=0;
        int count=0;
        counts.put(0,1);
        for (int j = 0; j < nums.length; j++) {
            sum+=nums[j];
            //如果存在sum-k的值
            if (counts.containsKey(sum-k)) {
                count+=counts.getOrDefault(sum-k,0);
            }
            counts.put(sum,counts.getOrDefault(sum,0)+1);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums={1,2,3};
        new UsingMap().subarraySum(nums,3);
    }
}

总结

通过Map可以以空间换取时间。