NC125. 和为K的连续子数组
描述
示例1
输入:
[1,-2,1,1,1],0
输出:
3
示例2
输入:
[0,1,2,3],3
输出:
3
C 解法, 执行用时: 15ms, 内存消耗: 2344KB, 提交时间: 2021-10-28
/**
* max length of the subarray sum = k
* @param arr int整型一维数组 the array
* @param arrLen int arr数组长度
* @param k int整型 target
* @return int整型
*/
int maxlenEqualK(int* arr, int arrLen, int k ) {
int i=0,j=0,t=0,sum=0;//,count=0;
if(arrLen<2)
{
return 0;
}
for(i=0;i<arrLen-1;++i)
{
//count=0;
sum=0;
for(j=0;j<arrLen-i;++j)
{
sum+=arr[j];
//count++;
}
if(j==arrLen && sum==k)
{
return j;
}
if(i>0)
{
if(sum==k)
return j;
else
{
t=0;
while(t<i)
{
sum=sum-arr[t++] + arr[j++];
if(sum==k)
return j-t;
}
}
}
}
return 0;
}
C++ 解法, 执行用时: 15ms, 内存消耗: 2660KB, 提交时间: 2021-08-17
class Solution {
public:
/**
* max length of the subarray sum = k
* @param arr int整型vector the array
* @param k int整型 target
* @return int整型
*/
int maxlenEqualK(vector<int>& arr, int k) {
int N=arr.size();
int res=0;
int i=0, j=0;
int sum=0;
int sum1=0;
for(i=0; i<N; i++){
if(arr[i] ==k && res<1) res=1;
sum+=arr[i];
if(sum==k && res < i+1) res=i+1;
}
sum1=sum;
int L=N-1;
while(L>0){
sum=sum1-arr[L];
sum1=sum;
if(sum == k && res < L){ res=L; break; }
int s=1, e=L;
while(e<N){
sum-=arr[s-1];
sum+=arr[e];
if(sum == k && res < L){ res=L; break; }
s++;
e++;
}
if(res == L){break;}
L--;
}
return res;
}
};
C++ 解法, 执行用时: 15ms, 内存消耗: 2700KB, 提交时间: 2021-07-25
static const auto io_sync_off=[](){
ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* max length of the subarray sum = k
* @param arr int整型vector the array
* @param k int整型 target
* @return int整型
*/
int maxlenEqualK(vector<int>& arr, int k) {
if(arr.size()==0)
return 0;
vector<int> sum(arr.size(),0);//累积数组
sum[0]=arr[0];//初始化第一个
unordered_map<int,int> mp;//存放前累积和 对应的下标
mp[sum[0]]=0;
for(int i=1;i<arr.size();i++)
{
sum[i]=sum[i-1]+arr[i]; //累积和
mp[sum[i]]=i;//该累积和的下标（由于i迭代增加 所以i存放的是最大的i）
}
int ans=0;
for(int i=0;i<arr.size()-1;i++)
{
if(mp.find(sum[i]+k)!=mp.end()) //查找当前累积和相差k的值是否存在
{
ans=max(ans,mp[sum[i]+k]-i);
}
}
//存在直接从0项开始累积和为k的
if(mp.find(k)!=mp.end())
ans=max(ans,mp[k]+1);
return ans;
}
};
C++ 解法, 执行用时: 15ms, 内存消耗: 2724KB, 提交时间: 2021-09-28
class Solution {
public:
/**
* max length of the subarray sum = k
* @param arr int整型vector the array
* @param k int整型 target
* @return int整型
*/
int maxlenEqualK(vector<int>& arr, int k) {
// write code here
int len = arr.size();
int sum[len + 1];
memset(sum, 0, sizeof(sum));
sum[1] = arr[0];
for (int f = 2; f <= len; f++)
{
sum[f] = sum[f - 1] + arr[f - 1];
}
bool flag = false;
while (len >= 1)
{
int i = 0;
int j = i + len - 1;
while (j < arr.size())
{
if (sum[j + 1] - sum[i] == k)
{
flag = true;
break;
}
i++;
j++;
}
if (flag) break;
len--;
}
return len;
}
};
C++ 解法, 执行用时: 15ms, 内存消耗: 2724KB, 提交时间: 2021-08-23
class Solution {
public:
/**
* max length of the subarray sum = k
* @param arr int整型vector the array
* @param k int整型 target
* @return int整型
*/
int maxlenEqualK(vector<int>& arr, int k) {
// write code here
/*
vector<int> a;
a.push_back(0);
int num = 0;
for(int i = 0 ; i < arr.size(); i++)
{
num+=arr[i];
a.push_back(num);
}
num = arr.size();
for(int i = num; i > 0; i--)
{
for(int j = 0; j < num-i+1; j++)
{
int k1 = a[j+i] - a[j];
if(k1==k) return i;
}
}
return 0;
*/
vector<int> s;
int sum = 0;
for(int i = 0;i < arr.size(); i++)
{
sum += arr[i];
s.push_back(sum);
}
int max = -1;
for(int i = arr.size()-1 ; i >=0 ; i--)
{
for(int j = 0; j < arr.size()-i ;j++)
{
int t;
if(j==0)
{
t = s[i];
}
else
{
t = s[j+i]-s[j-1];
}
if(t == k) return i+1;
}
}
return 0;
}
};