Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm N số nguyên đượ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 = 14
Output : subarray = {5, -1, 4, 6} Giải thích -
Subarray sum = 5 - 1 + 4 + 6 = 14
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 = 14;
findSubArrayWithSum(arr, n, sum);
return 0;
} Đầu ra
Subarray with given sum : { 5 -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 hashmap. Bản đồ băm sẽ lưu trữ tổng tiền tố cho đến chỉ mục hiện tại. Và đối với bất kỳ chỉ mục nào, hãy kiểm tra xem có tồn tại một mảng con với tổng hay không. Chúng tôi sẽ kiểm tra xem có tiền tố với sum =sum - value hay không.
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<<"}";
}
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;
} Đầu ra
Subarray with given sum : { 5 -1 4 6 }