LeetCode560 和为k的子数组

发表于 | 分类于 |
字数统计: 695 | 阅读时长 ≈ 3

链接: https://leetcode-cn.com/problems/subarray-sum-equals-k/

题意

给定一个数组，寻找和为 k 的连续区间个数。

解法

本来以为是个简单题 结果卡了快一下午
不过好歹还是学到点东西的 对前缀和理解更深了一点
有一些收获
本来以为前缀和是有序的，然后可以二分找到差值
结果调了很久发现行不通 因为前缀和并不是有序的 甚至还有可能有多个相同的值
白白浪费两个小时
暴力二重循环会在最后一个样例超时

然后考虑用map存储所有的前缀和和它们的下标，由于同一个值可能对应多个索引
所以需要用multimap存储 学习了一下multimap的用法
multimap找键值的时候不能用[]来进行访问 需要用equal_range函数找出所有key-pair
返回值是一个iterator的pair分别表示找到的头尾 再进行访问
如果出现的target在当前下标前就加到结果中
这样可以通过 但是效率很低

正确的方法是 不需要一下子存入所有的前缀和到map中
遍历的过程中 实时更新map键值 这样可以保证后面加进来的都是之前的前缀和
而不会出现后面的前缀和的情况

这样的做法下甚至可以不需要pre数组，只要一个变量存储前缀和就可以
这样解法下的代码很短 可以说是简洁而优雅

代码

multimap解法

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
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if (nums.empty()) return k == 0;
        int n = nums.size(), cnt = 0;
        vector<int> pre(n + 1);
        multimap<int, int> mp;
        mp.insert({0, 0});
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + nums[i - 1];
            mp.insert({pre[i], i});
        }
        for (int i = 1; i <= n; i++) {
            int target = pre[i] - k;
            auto pr = mp.equal_range(target);
            if(pr.first != mp.end())
            {
                for (auto iter = pr.first ; iter != pr.second; ++iter)
                {
                    if (iter->second < i) {
                        cnt++;
                    }
                    if (iter->second > i) {
                        break;
                    }
                }
            }
        }
        return cnt;
    }
};

前缀和数组解法

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) {
        if (nums.empty()) return k == 0;
        int n = nums.size(), cnt = 0;
        vector<int> pre(n + 1);
        unordered_map<int, int> mp;
        mp[0] = 1;
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            cnt += mp[pre[i] - k];
            mp[pre[i]]++;
        }
        return cnt;
    }
};

最优解法

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) {
        if (nums.empty()) return k == 0;
        int n = nums.size(), cnt = 0, presum = 0;
        unordered_map<int, int> mp;
        mp[0] = 1;
        for (int i = 1; i <= n; i++) {
            presum += nums[i - 1];
            cnt += mp[presum - k];
            ++mp[presum];
        }
        return cnt;
    }
};