Finding the sequential sub array totaling to the given number[reviewed]

Problem

Given an array of integer A = {23, 5, 4, 7,2, 11}, and the length N, and target sum, S, write the algorithm that tells whether the sub array $A_{sub}$, where $\sum_{i=k}^p A_{sub} (i) = S$.

For example, If N = 3, and S = 13, it should return sub array, {4,7, 2}.


Given the requirements to return the sub array of sequential numbers whose sum equals to S, we can use a  "Queue" like buffer with size of N while iterative over the numbers in the array, S.

Figure 1. Initial settings 

As shown in Figure 1, we initialize the two variable, "start" and "end" to 0 and N-1 respectively.
Of course, we should check if array A's size is larger than N, and compute the sum of A[0] ... A[N-1] and store it in Current sum.

The actual search start from N th element in the array.

If the current sum is not equal to S, we shift the current queue starting from "start" to "end" by 1.
Accordingly, we adjust the current sum as below:

    1. Subtract A[s] from the current sum.
    2. Add A[i] to the current sum

Figure, Second iteration after shifting by 1.

All we need to do is to repeat this process until either we reach the end of array, A or found the position, where current sum equals A.

Overall running time of this algorithm will be $O(N)$.

Here is the complete code running in $O(N)$

	#include<vector>
	#include<iostream>
	using namespace std;
	int sum(int* input, int s, int e)
	{
	int S = 0;
	for (int i = s; i <= e; i++)
	S += input[i];
	return S;
	}
	vector<int> find_sub_array(int * input, int len, int N, int S)
	{
	int s = 0;
	int e = N-1;
	vector<int> result;
	if ( len < N)
	return result;
	int cur = sum(input, s, e);
	for (int i = N; i < len; i++)
	{
	if (cur == S)
	{
	result.push_back(s);
	result.push_back(e);
	break;
	} else {
	cur -= input[s++];
	cur += input[i];
	e = i;
	}
	}
	return result;
	}
	int main() {
	int input[6] = {23, 5, 4, 7,2, 11};
	cout << "N = 3, S = 13 :"<<endl;
	vector<int> found = find_sub_array(input, 6, 3, 13);
	if (found.size() == 2)
	cout<<"sub array start =" << found[0] << ", end = "<< found[1]<<endl;
	else
	cout<< "not found"<<endl;
	found = find_sub_array(input, 6, 4, 19);
	cout << "N = 4, S = 19: "<<endl;
	if (found.size() == 2) cout<<"sub array start =" << found[0] << ", end = "<< found[1]<<endl;
	else
	cout<< "not found"<<endl;
	return 1;
	}

view raw find_seq_subarray.cpp hosted with ❤ by GitHub

Practice statistics

13:18.88 mins : to hand wrote the code.
5:45.03 mins: to write up in the IDE.


UPDATE(2019-07-26): solved the problem again.

Here is a solution in python.

	class FindSum:
	def find_subarray(self, A, N, S):
	s = None
	current_sum = 0
	result = []
	for i, v in enumerate(A):
	if s == None:
	s = i
	elif i - s + 1 == N:
	if current_sum + v == S:
	result = A[s :i+1]
	break
	else:
	#trim left by 1, shift the window to right.
	current_sum -= A[s]
	s += 1
	current_sum += v
	return result
	f = FindSum()
	input =[23, 5, 4, 7,2, 11]
	N = 3
	S = 13
	print("input = {} N = {} S = {} output = {}".format(input, N, S, f.find_subarray(input, N, S)))

view raw facebook_find_subarray_for_N_and_S_greedy.py hosted with ❤ by GitHub

Statistics:

9:00 for algorithm

11:00 to write up the code and fix two logic error after runnig the code. review the code before running. Need to be more careful.