数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
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 = 14
Output : subarray = {5, -1, 4, 6}解释 −
Subarray sum = 5 - 1 + 4 + 6 = 14
解决方案方法
解决这个问题的一个简单方法是使用嵌套循环。我们将遍历数组，并使用内循环查找子数组。对于每个子数组，我们将找到所有元素的和，并将其与给定的和值进行比较。如果相等，则打印子数组。如果遍历了数组的所有元素，则打印未找到这样的数组。
算法
步骤 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 = 14;
findSubArrayWithSum(arr, n, sum);
return 0;
}输出
Subarray with given sum : { 5 -1 4 6 }解决这个问题的更好方法是使用哈希表。哈希表将存储到当前索引的总和。对于任何索引，检查是否存在具有总和的子数组。我们将检查是否存在具有 sum = sum - value 的前缀。
示例
程序说明我们解决方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
cout<<"{ ";
for(; i <= j; i++)
cout<<arr[i]<<" ";
cout<<"}";
}
void findSubArrayWithSum(int arr[], int n, int sum) {
unordered_map<int, int> map;
int curr_sum = 0;
for (int i = 0; i < n; i++){
curr_sum = curr_sum + arr[i];
if (curr_sum == sum) {
cout<<"SubArray with the given sum :";
printSubArray(arr, 0, i);
return;
}
if (map.find(curr_sum - sum) != map.end()) {
cout<<"SubArray with the given sum : ";
printSubArray(arr, map[curr_sum - sum] + 1 , i);
return;
}
map[curr_sum] = i;
}
cout<<"No subarray found!";
}
int main() {
int arr[] = { 2, 5, -1, 4, 6, 9, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 14;
findSubArrayWithSum(arr, n, sum);
return 0;
}输出
SubArray with the given sum : { 5 -1 4 6 }
更新于：2022年1月25日
464 次查看
广告