Leetcode 560: Subarray Sum Equals K

发表于 更新于 分类于 阅读次数：

Problem

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

Solution

解题思路

本题不属于某类经典类型的算法题。本题的解题关键在于深刻理解子数组和的计算方法，以及和为K的子数组和个数的求解技巧。

首先，需要求得长度为n的数组的和为K的连续子数组的个数，设为A(n)。统计连续子数组的和，以及和的分布则成为解题的前提条件。在统计连续子数组的和的过程中，我们可以采用穷举法，将所有子数组的和都进行一次统计，也能运用一些巧妙的方法，只统计部分子数组的和的个数，计算出和为K的子数组和的个数。

为了达到优化子数组和统计的方法，可以仔细思考子数组和的计算方法。不难得出，子数组和的计算方法其实源于两个从零开始的数组和之差。也就是说，假设从A[m]到A[n]之间的子数组和S[mn] = S[0n] - S[0-m]。如果在已知S[0~i] (i=0,…,n-1)的值，就能轻松求解出所有子数组的和。

然而，这样的方法用于求所有的子数组的和，并不能简化计算复杂度。要找到和为K的子数组的个数，就等于需要便利S[0i] (i=0,…,n)，并且找出末尾为第i个元素的子数组序列和为K的个数。由此不难推出，末尾为第i个元素的子数组序列和为K的个数，等价于S[mi] (m=1,…,i-1)中和为K的个数，也等价于S[0m] (m=1,…,i-1)中和为S[0i]-K的子数组个数。

1
2
3
Number(末尾为第i个元素的子数组序列和为K的个数)=Number(S[0~m] (m=1,...,i-1)中和为S[0~i]-K的子数组个数);

Number(n长数组子数组序列和为K的个数)=sigma(Number(末尾为第i个元素的子数组序列和为K的个数)) (i=0,...n-1)

程序设计

本题解的优劣则取决于统计子数组和的计算量。

  1. 运用hashmap数据结构存取所有的子数组和，经过两次for循环遍历得出所有子数组可能性下的和的值，并统计入hashmap中。本解法的时间复杂度是O(n^2)。
  2. 优化后的算法采用hashmap数据结构存取S[0~i] (i=0,…n-1)，并且在每次计算后计算以i结尾的连续子数组和为K的个数。将所有数字相加则为综合。本解法的时间复杂度是O(n)。

实现技巧

边界条件考虑：

  • K=0的情况。
  • K=S[0~i] (i=0,…,n-1)中的任意一个情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer> ();
        int sum = 0;
        int total =0;
        for(int i = 0; i< nums.length; ++i){
            sum += nums[i];  
            // don't forget margin k = 0, check previous count before adding this count to avoid confustion.
            if( map.containsKey(sum-k))
                total += map.get(sum-k);
            if(k == sum)
                total += 1;
               
            if(map.containsKey(sum))
                map.put(sum, map.get(sum)+1);
            else
                map.put(sum, 1);                
        }
        return total;
    }
}