数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中查找具有给定和的子数组 - （非负数）
在这个问题中，我们得到一个包含 N 个正整数的数组 arr[]，这些整数以无序的方式存储。我们的任务是查找具有给定和的子数组。
让我们举个例子来理解这个问题，
Input : arr[] = {2, 5, 1, 4, 6, 9, 5} sum = 11
Output : subarray = {1, 4, 6}说明 -
Subarray sum = 1 + 4 + 6 = 11
解决方案方法
解决该问题的一个简单解决方案是使用嵌套循环。我们将遍历数组，并使用内部循环查找子数组。对于每个子数组，我们将找到所有元素的总和并将其与给定的总和值进行比较。如果相等，则打印子数组。如果遍历了数组的所有元素，则打印未找到此类数组。
算法
步骤 1 - 遍历数组，i -> 0 到 (n-1)。
步骤 1.1 - 对于每个元素，查找所有可能的子数组的每个子数组的总和。
步骤 1.2 - 如果当前子数组元素的总和等于给定的子数组，则打印子数组。
步骤 2 - 如果遍历了数组的所有元素并且未找到子数组。打印“未找到具有给定和的子数组！”。
示例
程序说明我们解决方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
cout<<"{";
for(; i < j; i++)
cout<<arr[i]<<" ";
cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
int currSum;
for (int i = 0; i < n; i++) {
currSum = arr[i];
for (int j = i + 1; j <= n; j++) {
if (currSum == sum) {
cout<<"Subarray with given sum : ";
printSumArray(arr, i, j); return 1;
}
if (currSum > sum || j == n)
break;
currSum = currSum + arr[j];
}
}
cout<<"No subarray found";
return 0;
}
int main() {
int arr[] = { 2, 5, 1, 4, 6, 9, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 11;
findSubArrayWithSum(arr, n, sum);
return 0;
}输出
Subarray with given sum : { 1 4 6 }解决该问题的一个更好的方法是使用类似于滑动窗口的方法，但在这里我们将有一个可变窗口。我们将从数组的第一个元素开始，将元素添加到窗口中，直到总和大于给定的总和。如果它变得大于，则删除元素，直到它再次小于总和。执行此过程，直到整个数组被遍历。
如果在任何时候，窗口总和等于给定的总和，则打印子数组。如果没有找到窗口总和等于给定总和的窗口，并且没有元素要遍历，则打印“未找到子数组！”。
算法
初始化 - windowSum = 0，sindex = 0，endindex = 0
步骤 1 - 使用 endindex 遍历数组。
步骤 1.1 - 通过添加元素来更新 windowSum，直到 windowSum 大于 sum，即 if(windowSum < sum) -> windowSum = windowSum + arr[endIndex]。
步骤 1.2 - 如果 windowSum 大于 sum，则通过删除元素来减小窗口大小，即 while(windowSum < sum) -> windowSum = windowSum - arr[endIndex]。
步骤 1.3 - 如果 windowSum == sum，则打印子数组。
步骤 2 - 如果数组被遍历，则打印 -> '不可能'。
示例
程序说明我们解决方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
cout<<"{ ";
for(; i < j; i++)
cout<<arr[i]<<" ";
cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
int windowSum = arr[0], startIndex = 0, endIndex;
for (endIndex = 1; endIndex <= n; endIndex++) {
while (windowSum > sum && startIndex < endIndex - 1) {
windowSum -= arr[startIndex];
startIndex++;
}
if (windowSum == sum) {
cout << "Subarray with given sum : ";
printSumArray(arr, startIndex ,endIndex);
return 1;
}
if (endIndex < n)
windowSum += arr[endIndex];
}
cout << "No subarray found";
return 0;
}
int main() {
int arr[] = { 2, 5, 1, 4, 6, 9, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 11;
findSubArrayWithSum(arr, n, sum);
return 0;
}输出
Subarray with given sum : { 1 4 6 }
343 次查看
