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

​ 题意：给出一个数列，找出其连续的子序列之和为k的可能种数。

​ 其实就是找出a[i]到a[j]之和为k有多少种可能，我想到就是纯粹的暴力做法，遍历i和j（i<=j<=nums.size()）的所有可能性求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if(!nums.size())
            return 0;
        int len = nums.size();
        int ans = 0;
        int sum;

        for (int i = 1; i <= len; ++i)
        {
            sum = 0;
            for (int j = i; j <= len; ++j)
            {
                sum += nums[j - 1];
                if(sum==k)
                    ans++;
            }
        }
        return ans;
    }
};

​ 复杂度为O（N^2）一开始以为会超时，没想到竟然能通过。但是肯定不能满足于O（N^2）的做法，所以看了下Discussion发现大佬还是有O（N）的做法的。

​ 因为这里要求的是sum[i…j]，这里是连续的，所以不需要每次都遍历逐项相加。利用前缀和就可以简便好多。

​ sum[i…j] = preSum[j] - preSum[i-1]

​ 所以我们只需遍历一遍数组，假设遍历到了a[i]，那么此时sum就是preSum[i]，那么就只需要找一找在i之前有没有哪个前缀和为为sum-k（FindNum）就可以咯~

​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        map<int, int> preSum;//preSum<a,b>:前缀和为a的有b种可能
        int ans = 0;
        int sum = 0;
        int findNum;
        preSum[0]++;
        for (int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            findNum = sum - k;
            ans += preSum[findNum];
            preSum[sum]++;
        }
        return ans;
    }
};