卡在这个问题上看不懂子数组求和的代码
Stuck in this question and couldn't understand the code for the sum of subarray
我卡在了问题的结束函数部分,arr[start]/arr[end] 以及我无法理解代码。题目如下:
Given an unsorted array A of size N that contains only non-negative
integers, find a continuous sub-array which adds to a given number S.
You don't need to read input or print anything. The task is to
complete the function subarraySum() which takes arr, N and S as input
parameters and returns a list containing the starting and ending
positions of the first such occurring subarray from the left where sum
equals to S. The two indexes in the list should be according to
1-based indexing. If no such subarray is found, return -1.
def subArraySum(arr,n,sum):
curr_sum = 0
start = 0
end=0
i = 0
while end <= n-1:
if curr_sum<sum:
curr_sum=curr_sum+arr[end]
end=end+1
while curr_sum>sum:
curr_sum=curr_sum-arr[start]
start=start+1
if curr_sum==sum:
break
if curr_sum != sum:
return[-1]
else:
return start+1, end
此代码正在寻找最早的连续序列加起来等于给定的数字。例如:
1 1 2 4 5 2
是6个数字的序列。如果我们正在寻找第一个与 7 相加的序列,我们最终会在由两个索引 start
和 end
:
定义的子序列中得到 1、2 和 4
start|
1 1 2 4 5 2
end|
请注意,end
是最后一个。这是一个共同的约定。同样在任何给定时间,curr_sum
是子序列中所有数字的总和。在上面的例子中,7.
代码以 start
和 end
在 0 处开始。随着代码循环,如果当前子序列 curr_sum
的总和小于所需的总和,则它通过将 end
向上移动一个,使子序列从前端更长。如果 curr_sum
太大,它会根据需要多次向上移动 start
来缩短子序列。如果 curr_sum
是正确的总和,那么它会中断函数并且 returns start
和 end
索引。
综上所述,您可以通过不同的方式跟踪此处的索引。尽我所能,子序列由从 start
到 end
的基于 0 的索引定义,但不包括 end
。然后在最后,它包含结束索引的基于 returns 1 的索引,这就是为什么它使用 start+1, end
而不是 start, end
.
vector<int> subarraySum(int arr[], int n, long long s)
{
int i=0;
int j=0;
long currSum=0;
while(i<n);
if (currSum==s){
return{i+1,j};
}
if(currSum<s){
currSum+=arr[j];
j++;
}
else{
currSum-=arr[i];
i++;
}
vector<int>v;
v.push_back(-1);
return v;
}
};
我卡在了问题的结束函数部分,arr[start]/arr[end] 以及我无法理解代码。题目如下:
Given an unsorted array A of size N that contains only non-negative integers, find a continuous sub-array which adds to a given number S.
You don't need to read input or print anything. The task is to complete the function subarraySum() which takes arr, N and S as input parameters and returns a list containing the starting and ending positions of the first such occurring subarray from the left where sum equals to S. The two indexes in the list should be according to 1-based indexing. If no such subarray is found, return -1.
def subArraySum(arr,n,sum):
curr_sum = 0
start = 0
end=0
i = 0
while end <= n-1:
if curr_sum<sum:
curr_sum=curr_sum+arr[end]
end=end+1
while curr_sum>sum:
curr_sum=curr_sum-arr[start]
start=start+1
if curr_sum==sum:
break
if curr_sum != sum:
return[-1]
else:
return start+1, end
此代码正在寻找最早的连续序列加起来等于给定的数字。例如:
1 1 2 4 5 2
是6个数字的序列。如果我们正在寻找第一个与 7 相加的序列,我们最终会在由两个索引 start
和 end
:
start|
1 1 2 4 5 2
end|
请注意,end
是最后一个。这是一个共同的约定。同样在任何给定时间,curr_sum
是子序列中所有数字的总和。在上面的例子中,7.
代码以 start
和 end
在 0 处开始。随着代码循环,如果当前子序列 curr_sum
的总和小于所需的总和,则它通过将 end
向上移动一个,使子序列从前端更长。如果 curr_sum
太大,它会根据需要多次向上移动 start
来缩短子序列。如果 curr_sum
是正确的总和,那么它会中断函数并且 returns start
和 end
索引。
综上所述,您可以通过不同的方式跟踪此处的索引。尽我所能,子序列由从 start
到 end
的基于 0 的索引定义,但不包括 end
。然后在最后,它包含结束索引的基于 returns 1 的索引,这就是为什么它使用 start+1, end
而不是 start, end
.
vector<int> subarraySum(int arr[], int n, long long s)
{
int i=0;
int j=0;
long currSum=0;
while(i<n);
if (currSum==s){
return{i+1,j};
}
if(currSum<s){
currSum+=arr[j];
j++;
}
else{
currSum-=arr[i];
i++;
}
vector<int>v;
v.push_back(-1);
return v;
}
};