The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

Problem :-
Given an array of 'n' elements & and a window of size 'p', find if there exists a subarray of consecutive elements of size 'p' which sums to a given value 'x'.
Consider array { 2, 4, -3, 7, -1} ,
Window size = 3 & Target value = 8
We see that subarray = { 4, -3, 7 } of size 3 has sum = 8

Solution :-
We will follow a sliding window approach i.e consider the window of size p starting at index 0.
If the sum of all elements within the window is not equal to 'x', then shift the window by one position towards right.
See the efficient implementation below.

#include<iostream>using namespace std;
// find a window of size 'p' with sum of elements = targetbool isSubarrayPresent(int arr[],int size,int p,int target) {
int i;
// start and end index of window of size 'p'int start_window_idx = 0;
int end_window_idx = 0;
int sum = 0;
for (i=0;i<size;i++) {
sum += arr[i];
end_window_idx++;
if (sum == target && (end_window_idx - start_window_idx) == p) {
// window of 'p' elements with sum = target foundreturn true;
}
if ((end_window_idx - start_window_idx) == p) {
// sum of elements in current window is not equal to target
// shift the window by one position
sum -= arr[start_window_idx];
start_window_idx++;
}
}
return false;
}
// mainint main() {
int arr[] = { 1,4,-2,6,-3,7,1,3,-6,1 };
int size = sizeof(arr)/sizeof(arr[0]);
int p = 4;
int target = -1;
bool found = isSubarrayPresent(arr,size,p,target);
if (found) {
cout<<"\nSubarray of "<<p<<" elements with sum "<<target<<" found";
} else {
cout<<"\nSubarray of "<<p<<" elements with sum "<<target<<" not found";
}
cout<<endl;
return 0;
}

#include<iostream>using namespace std;
// find a window of size 'p' with sum of elements = targetbool isSubarrayPresent(int arr[],int size,int p,int target) {
int i;
// start and end index of window of size 'p'int start_window_idx = 0;
int end_window_idx = 0;
int sum = 0;
for (i=0;i<size;i++) {
sum += arr[i];
end_window_idx++;
if (sum == target && (end_window_idx - start_window_idx) == p) {
// window of 'p' elements with sum = target foundreturn true;
}
if ((end_window_idx - start_window_idx) == p) {
// sum of elements in current window is not equal to target
// shift the window by one position
sum -= arr[start_window_idx];
start_window_idx++;
}
}
return false;
}
// mainint main() {
int arr[] = { 1,4,-2,6,-3,7,1,3,-6,1 };
int size = sizeof(arr)/sizeof(arr[0]);
int p = 4;
int target = -1;
bool found = isSubarrayPresent(arr,size,p,target);
if (found) {
cout<<"\nSubarray of "<<p<<" elements with sum "<<target<<" found";
} else {
cout<<"\nSubarray of "<<p<<" elements with sum "<<target<<" not found";
}
cout<<endl;
return 0;
}