資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告