Trong bài toán này, chúng ta được cung cấp một mảng arr [] bao gồm N số nguyên dương được lưu trữ theo thứ tự không được sắp xếp. Nhiệm vụ của chúng ta là tìm một mảng con có tổng cho trước .
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {2, 5, 1, 4, 6, 9, 5} sum = 11
Output : subarray = {1, 4, 6} Giải thích -
Subarray sum = 1 + 4 + 6 = 11
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng các vòng lặp lồng nhau. Chúng ta sẽ lặp qua mảng và sử dụng một vòng lặp bên trong, chúng ta sẽ tìm thấy mảng con. Đối với mỗi mảng con, chúng ta sẽ tìm tổng của tất cả các phần tử và so sánh nó với giá trị tổng đã cho. Nếu nó bằng nhau, hãy in mảng con. Nếu tất cả các phần tử của mảng được duyệt qua, hãy in ra không tìm thấy mảng nào như vậy.
Thuật toán
-
Bước 1 - Lặp qua mảng, i -> 0 đến (n-1).
-
Bước 1.1 - Đối với mỗi phần tử, hãy tìm tổng của mỗi mảng con cho tất cả các mảng con có thể có.
-
Bước 1.2 - nếu tổng các phần tử mảng tổng hiện tại bằng mảng con đã cho, hãy in mảng con đó.
-
-
Bước 2 - Nếu tất cả các phần tử của mảng được duyệt và không tìm thấy mảng con nào. In "Không tìm thấy mảng con nào với tổng đã cho!".
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
Subarray with given sum : { 1 4 6 } Một cách tiếp cận tốt hơn để giải quyết vấn đề là sử dụng một phương pháp tương tự như cửa sổ trượt nhưng ở đây chúng ta sẽ có một cửa sổ biến đổi. Chúng ta sẽ bắt đầu từ phần tử đầu tiên của mảng, thêm các phần tử vào cửa sổ cho đến khi tổng lớn hơn tổng đã cho. Nếu nó trở nên lớn hơn, hãy loại bỏ các phần tử cho đến khi nó trở nên nhỏ hơn tổng một lần nữa. Thực hiện quá trình này cho đến khi toàn bộ mảng được duyệt qua.
Nếu tại bất kỳ thời điểm nào, tổng cửa sổ trở nên bằng tổng đã cho, hãy in ra mảng con. Và nếu không tìm thấy cửa sổ nào có tổng bằng tổng đã cho và không có phần tử nào được duyệt qua, hãy in "Không tìm thấy mảng con nào!" .
Thuật toán
Khởi tạo - windowSum =0, sindex =0, endindex =0
-
Bước 1 - Duyệt mảng bằng endindex.
-
Bước 1.1 −Cập nhật windowSum bằng cách thêm các phần tử cho đến khi windowSum lớn hơn tổng, tức là if (windowSum
-
Bước 1.2 - Nếu windowSum lớn hơn sum, hãy giảm kích thước cửa sổ bằng cách xóa các phần tử, tức là while (windowSum
-
Bước 1.3 - if windowSum ==sum, print subarray.
-
-
Bước 2 - Nếu mảng được duyệt qua, hãy in -> 'không thể'.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
Subarray with given sum : { 1 4 6 }