LeetCode|560. 和为K的子数组--C++题解

Vaccae

发布于 2020-05-25 15:34:06

4340

发布于 2020-05-25 15:34:06

文章被收录于专栏：微卡智享

学更好的别人，

做更好的自己。

——《微卡智享》

本文长度为1543字，预计阅读4分钟

前言

本题原本按我最喜欢的暴力破解提交的，结果到最后几个大数据的时候提示超时了，最后也是看了官方的思路，了解了动态规划的思路去解的这个题，所以本篇写了两个实现的方法。。

视频演示

题目

微卡智享

解题方式

微卡智享

暴力破解

#	解法
1	循环遍历数组中的每一个数
2	在上一步循环的当前数中对当前数及后续的数进行递归计算
3	计算到不再是我们要求的和后退出当然数再跳到下一个数

暴力破解代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        if(nums.size() < 1) return count;
        
        for(int i = 0; i < nums.size(); ++i){
           count += addcount(k, nums, i);                 
        }
        return count;
    }

    int addcount(int k,vector<int>& nums, int pos){
        int rescount = 0;
        if(nums.size() == pos) return rescount;
        if(nums[pos] == k) rescount++;
        rescount += addcount(k - nums[pos], nums, pos + 1);

        return rescount;
    }
};

TIPS

上面的暴力解法可以解决基本的问题，不过在我提交后，在第69个测试用例超大数时，提示超时了，如下图

因为这问题超时就算没通过，于是研究了一下官方的解题思路，有了下面的解法二--动态规划。

动态规划

首先说，这个解题思路真是了看了官方的解题思路后才真是恍然大悟，发现这个解法真的是很巧妙。

#	解法
1	创建一个Hash散列表，用于存储当前循环到的数的和。并创建初始值为0的添加进散列表
2	循环遍历数组的数（同暴力法相同），计算遍历到挡前数的和
3	用当前的和减去我们求到的和的值，去寻找Hash散列表中是否存在减后的值对应的数，如果存在输入值+1，不存在就写入散列表
4	跳到下一个数后重复第2步，直到结束

上面的步骤可能这样看文字还是不太理解，推荐大家看一下上面视频，上面的实现步骤有动画效果的展示，看了后应该能明白。（提高自己输出东西的质量，以后我也尽量以视频为主，文章贴代码或相关的一些来实现，题外话，写文章还是快，做一个视频动画效果有时候一下子就一天过去了，不过这样我觉得感观上吸收应该会更好，所以会坚持这样下去）

动态规划的代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {

        unordered_map<int,int> maps;    
        //第一位前缀合肯定是0，默认值为1    
        maps[0] = 1;  

        int count = 0;
        int sum = 0;

        for(int i = 0; i < nums.size(); ++i){
           sum += nums[i];
           if(maps.find(sum - k) != maps.end()) count += maps[sum - k];
           maps[sum]++;               
        }
        return count;
    }

};

上面代码看比暴力解法更简洁，还更容易，但是想到这一步真的是经过倒推很久才发现的这个巧妙，而且我最近在学数据结构和算法时，也遇到了动态规划的问题，这个真的是需要大量的练习才能提高的，给自己加个油。

提交记录