Trong bài toán này, chúng ta được cho một mảng arr[] gồm N số nguyên lưu trữ theo thứ tự không sắp xếp. Nhiệm vụ của chúng ta là tìm một con mảng với tổng cho trước.
Hãy xem ví dụ sau để hiểu bài toán:
Input : arr[] = {2, 5, -1, 4, 6, -9, 5} sum = 14 Output : subarray = {5, -1, 4, 6}Giải thích −
Tổng con mảng = 5 - 1 + 4 + 6 = 14
Phương pháp giải
Một giải pháp đơn giản là sử dụng vòng lặp lồng nhau. Ta sẽ lặp qua mảng và dùng vòng lặp trong để tìm con mảng. Với mỗi con mảng, ta tính tổng các phần tử và so sánh với tổng cho trước. Nếu bằng nhau, in con mảng. Nếu duyệt hết mảng, in không tìm thấy.
Thuật toán
Bước 1 − Lặp qua mảng, i -> 0 đến (n-1).
Bước 1.1 − Với mỗi phần tử, tìm tổng của mỗi con mảng cho tất cả con mảng có thể.
Bước 1.2 − Nếu tổng con mảng hiện tại bằng tổng cho trước, in con mảng.
Bước 2 − Nếu duyệt hết mảng và không tìm thấy con mảng. In "Không tìm thấy con mảng với tổng cho trước!".
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
Subarray with given sum : { 5 -1 4 6 }Một phương pháp tốt hơn là sử dụng hashmap. Hashmap sẽ lưu tổng tiền tố đến chỉ số hiện tại. Với bất kỳ chỉ số nào, kiểm tra xem có tồn tại con mảng với tổng đó. Ta kiểm tra xem có tiền tố nào với tổng = sum - giá trị.
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
SubArray with the given sum : { 5 -1 4 6 }