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:

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

最朴素且有问题的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        map<int, int> mp;
        mp[0] = -1;	// 记录第一个满足子数组和为0的位置
        int cnt = 0;
        int sum = 0;
        for(int i=0;i<nums.size();++i){
            sum += nums[i];
            if(mp.find(sum - k)!=mp.end()){
                ++cnt;
            }
            mp[sum] = i;
        }
        return cnt;
    }
};

代码提交结果：62 / 80 test cases passed.

Input:[0,0,0,0,0,0,0,0,0,0] 0
Output:10
Expected:55

这个解法的问题在于未考虑到当子数组以nums[i]结尾时，存在多个子数组满足子数组和为sum - k。在这个思路的基础上进行修改，可以得到解法3。

解法1: 遍历子数组

当给定i时, sum 表示以arr[i]开始,到arr[j]结束的各个元素的累加和(j>=i).

注意: 这里不需要知道是哪些子数组的和等于k,只需要统计和等于k的子数组的个数,因此这里不必记录子数组的开始和结束索引,只需要依次找出所有子数组,并统计其中和等于k的子数组的个数.

那么如何找出所有可能的子数组呢?

方法一:内存循环找出所有以数组中第i个元素开始的所有子数组,并统计其中和等于k的子数组的个数.而外层循环则依次枚举所有可能的i.

方法二: 下面给出的代码是内层循环统计以数组中第j个元素结尾的子数组的和等于k的子数组的个数, 外层循环列举所有可能的j.
具体而言, 内层循环依次计算

arr[j]
arr[j-1] + arr[j]
arr[j-2] + arr[j-1] + arr[j]
…….
arr[2] + … + arr[j]
arr[1] + arr[2] + … + arr[j]

也就是子数组arr[i,..,j]的和. i = j, j-1,…1
若令s[i] 表示arr[1] + arr[2] + … + arr[i]
那么子数组arr[i,…j]的和可以表示为s[j] - s[i-1]

AC代码１

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0, counter = 0;
        for(int i=0;i<nums.size();i++){
            sum = 0;
            for(int j=i;j<nums.size();j++){
                sum += nums[j];
                if(sum == k)
                    ++counter;
            }
        }
        return counter;
    }
};

AC代码2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0, counter = 0;
        for(int j=0;j<nums.size();j++){
            sum = 0;
            for(int i=j;i>=0;i--){
                sum += nums[i];
                if(sum == k){
                    ++counter;
                }
            }
        }
        return counter;
    }
};

时间复杂度分析

时间复杂度: O(n2). 只用到两重循环, 容易得出时间复杂度
空间复杂度:O(1)

解法2

如方法二所述, 子数组arr[i, … , j]的和可以表示为s[j] - s[i-1]
s[0] = arr[0]
这里为了表示空数组的和为0, 不妨令s的下标从1开始.即

s[0] = 0, 表示空数组的和为0
s[1] = arr[0]
s[2] = arr[0] + arr[1]
s[3] = arr[0] + arr[1] + arr[2]

依次类推.

那么各子数组的和可以表示为

arr[0] = s[1] - s[0]
arr[0,1] = arr[0] + arr[1] = s[2] - s[0]
arr[1] = s[2] - s[1]
arr[1,3] = arr[1] + arr[2] + arr[3] = s[4] - s[1]

以此类推,可知

arr[i,….,j] = s[j+1] - s[i]

若要子数组arr[i,…,j]的和等于k,即s[j+1] - s[i] = k, 即s[i] = s[j+1] - k, 即当已知arr[1,…j]时只需要统计其前面的子数组中和等于s[j+1] - k的子数组的个数就可以统计以第j个元素结尾的子数组中满足和等于k的子数组的个数.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0, counter = 0;
        vector<int> temp;
        temp.push_back(0);
        for(int j=0;j<nums.size();j++){
            sum += nums[j];
            
            // 统计s[0], s[1], s[2],..,s[j]中和等于s[j+1] - k
            for(int i=0;i<temp.size();i++){
                if(sum - temp[i] == k){
                    ++counter;
                }
            }
            temp.push_back(sum);
        }
        return counter;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

可以看到这里的内层使用遍历的方法来统计数组中满足条件的子数组个数.但实际上,我们并不关心哪些子数组满足条件,而只需要知道满足条件的子数组个数,也就是说,我们不必记录s[j+1]之前的每个s[i](i<=j)具体由哪些元素组成, 我们只需要记住,s[i]有哪些可能的值及这些可能值出现的次数.
因此,我们可以使用map来记录每个值出现的次数.而从map中取出一个key对应的值只需要常量时间,通过这种方式可以大大降低所需时间.具体代码见下面代码.

解法3: 使用map

在最朴素的思路基础上，使用mp[i]表示子数组和为i的子数组个数。然后统计，当子数组以nums[i]结尾，且子数组nums[0]-nums[i]的和为sum时，以nums[j](j<i)结尾且和为sum - k的子数组个数，这就是以nums[i]结尾且何为k的子数组个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0;
        map<int, int> mp;
        mp[0] = 1;
        int cnt = 0;
        for(int j=0;j<nums.size();j++){
            sum += nums[j];
            if(mp.find(sum - k)!=mp.end()){
                cnt += mp[sum -k];
            }
            ++mp[sum];
        }
        return cnt;
    }
};

mp[sum -k]统计的是arr[i]之前的s[j]是否等于 sum - k.则s[i] - s[j] = arr[j+1] + arr[j+2] + .. + arr[i] = k.
这样同样需要注意需要额外设置mp[0] = 1; 表示存在空子数组的和为0.
复杂度分析

时间复杂度为O(n).空间复杂度为O(n).

要统计多少个子数组的和为k,则可以分别统计以数组中每个元素结尾的子数组中有多少个子数组的和等于k.