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