欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

560. 和为K的子数组

程序员文章站 2022-04-17 13:25:38
...

Q:

560. 和为K的子数组

A:

1.暴力找所有可能的子数组,n^2个子数组,最长长度n,则n ^3。
2.n^2解法
从1~n-1各起点开始,一直找到结尾,n^2

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

或者
保存前i个元素的和,子数组共有n^2种,对于i到j的子数组,可以用sum[j]-sum[i-1]求得,也是n ^2

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if(nums.empty()){return 0;}
        int siz=nums.size(),res=0;
        vector<int> sum(siz,0);
        sum[0]=nums[0];
        for(int i=1;i<siz;++i){
            sum[i]=sum[i-1]+nums[i];
        }
        for(int i=0;i<siz;++i){
            for(int j=i;j<siz;++j){
                if(i>0 and sum[j]-sum[i-1]==k){
                    res+=1;
                }
                else if(i==0 and sum[j]==k){
                    res+=1;
                }
            }
        }
        return res;
    }
};

3.O(N)解法,这个我没想出来,是用哈希表模拟动态规划的一个做法。
建一个map,i从0到n-1,对于所有从0开始到i的元素和都加入map,键为元素和,值为出现次数。
下面考虑任何一个所求解,假设左边界i,右边界j,i到j子数组的元素和为k。
那么就有前j项和减前i-1项和等于k,但是对于所有可能的i,j组合还是有n^2种可能。这里是利用map取指定键的对应值时间是O(1)。遍历到i时,即已经求出前i项元素和所有j(j<i)的前j项和。那么我们直接去map里查sum[i]-k在不在map里,在的话说明存在j(j<i)满足,sum[j]=sum[i]-k。 那么显然j+1到i的子数组的元素和就是k。当然如果sum[i]-k的值不止为1,说明有多个j(j<i)满足sum[j]=sum[i]-k,也就是有多个不同的j到i子数组满足元素和为k。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        map<int,int> dic;
        dic[0]=1;
        int sum=0,res=0;
        for(int i=0;i<nums.size();++i){
            sum+=nums[i];
            res+=dic[sum-k];//这步在前
            dic[sum]+=1;//这步在后,可能k==0,颠倒上下语句顺序会多算一个
        }
        return res;
    }
};
相关标签: c++ leetcode

推荐阅读