对于给定的输入数组,我们可以在线性时间内找到一个子数组,其总和为给定的K值,方法是通过跟踪当前已发现的总和和起始位置。如果当前的总和大于K,我们将删除从起始位置开始的元素,直到当前总和小于等于K。
我从geeksforgeeks找到了示例代码,并更新了它以返回所有可能的集合。但假设输入数组仅由正数组成。
bool subArraySum(int arr[], int n, int sum)
{
int curr_sum = 0, start = 0, i;
bool found = false;
for (i = 0; i <= n; i++)
{
while (curr_sum > sum && start < i)
{
curr_sum = curr_sum - arr[start];
start++;
}
if (curr_sum == sum)
{
cout<<"Sum found in b/w indices: "<<start<<" & "<<(i-1)<<"\n";
curr_sum -= arr[start];
start++;
found = true;
}
// Add this element to curr_sum
if (i < n) {
curr_sum = curr_sum + arr[i];
}
}
return found;
}
我的问题是,我们是否也有针对混合数字集(包括正数和负数)的解决方案?