560. 和为K的子数组
程序员文章站
2022-04-17 13:25:38
...
Q:
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;
}
};
推荐阅读
-
不能使用for循环,传入n和m,生成一个长度为n,每一项都是m的数组
-
程序员代码面试指南 python实现(第一章 栈和队列 :最大值减去最小值小于或等于num的子数组数量)
-
LeetCode 1 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
编写计算并输出一个3*3阶矩阵对角线元素的和。 程序运行结果示例: 请输入数组元素:(3*3)↙ 1 2 3 4 5 6 7 8 9↙ ↙ 数组为:cqupt
-
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
-
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的 两个 整数。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素
-
两数之和:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。...
-
c语言和Java语言实现,两数之和:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
[每日一题]给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。
-
算法(C++):给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数