Trong bài toán này, chúng ta được cho một mảng arr[] gồm N số nguyên dương 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 = 11 Output : subarray = {1, 4, 6}Giải thích −
Tổng con mảng = 1 + 4 + 6 = 11
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 = 11; findSubArrayWithSum(arr, n, sum); return 0; }Kết quả
Subarray with given sum : { 1 4 6 }Một phương pháp tốt hơn là sử dụng phương pháp tương tự cửa sổ trượt nhưng ở đây ta có cửa sổ biến đổi. Ta bắt đầu từ phần tử đầu tiên, thêm phần tử vào cửa sổ cho đến khi tổng lớn hơn tổng cho trước. Nếu lớn hơn, loại bỏ phần tử cho đến khi tổng nhỏ hơn lại. Lặp lại cho đến khi duyệt hết mảng.
Nếu tại bất kỳ thời điểm nào tổng cửa sổ bằng tổng cho trước, in con mảng. Và nếu không tìm thấy cửa sổ nào và không còn phần tử để duyệt, in "Không tìm thấy con mảng!".
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 phần tử cho đến khi windowSum lớn hơn sum, tức là if(windowSum < sum) -> windowSum = windowSum + arr[endIndex].
Bước 1.2 − Nếu windowSum lớn hơn sum, giảm kích thước cửa sổ bằng cách loại bỏ phần tử, tức là while(windowSum < sum) -> windowSum = windowSum - arr[endIndex].
Bước 1.3 − Nếu windowSum == sum, in con mảng.
Bước 2 − Nếu mảng đã duyệt xong, in -> 'không thể'.
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 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; }Kết quả
Subarray with given sum : { 1 4 6 }