leetcode [560. 和为K的子数组]

2021-01-21 08:13

阅读：809

标签：pre ble ++ http size vector als 连续 return

(https://leetcode-cn.com/problems/subarray-sum-equals-k/)

1：暴力法：因为要求的子数组必须是连续的，所以答案肯定是某一大块减去某一小块的结果正好为k，这样就自然而然的想到前缀和，得到前缀和在暴力枚举就行了，算法复杂度O(n²)，我的代码卡在了最后一组数据

class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int n = nums.size();
        vector add(n+1,0);
        for(int i = 1; i

2：前缀和加map优化：我们在利用上一个方法的add[i] - add[j] == k，移项可得到add[j] = add[i]-k ，我们发现暴力方法的时间都浪费在找add[j] 上了，所以我们可以利用一个map来记录add[i] 前的所有前缀和，如果在map中能找到add[i]-k ，我们就加上对应的个数

class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int n = nums.size();
        map M;
        M[0] = 1;
        int ans = 0,cnt = 0;
        for(int i = 0; i

这个值得说的是，这里的是一步一步求得前缀和，不像我的暴力法中一下子把所有前缀和都给求出来了，这样得好处是对于每个i对应得前缀和，此时map里存的是他前面的所有前缀和，这样才能保证其正确性

leetcode [560. 和为K的子数组]

标签：pre ble ++ http size vector als 连续 return

原文地址：https://www.cnblogs.com/Beic233/p/12897722.html

上一篇：关于python环境的一切注意事项

下一篇：Spring框架概述

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：leetcode [560. 和为K的子数组]
文章链接：http://soscw.com/index.php/essay/44899.html

亲，登录后才可以留言！

leetcode [560. 和为K的子数组]

评论

热门文章

推荐文章

最新文章

置顶文章