# Algorithmic complexity of Sub-array with sum = target algorithm

Question: Given an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X

E.g: If array is [1, 3, 5, 18] and X = 8 Output: True, if X = 10, output is FALSE.

Approach I can think of is to expand sub-array window, until you hit an index such that sum of sub-array == target or > target. If > target, decrease sub-array by moving first element to the right.

It appears that in worst-case complexity is O(N) since I am moving either start or end index of sub-arrays, so int worst case I will just spend 2*N iterations. Is that correct analysis?

BOOL checkIfArrHasSum(long *arr, size_t size; long target)
{
long currSum = [arr[0] longValue];
long startInd = 0;
long nextIndToCheck = 1;

while (nextIndToCheck < size)
{
if(currSum == target) return YES;

if (currSum + arr[nextIndToCheck] == target)
return YES;
else if(currSum + arr[nextIndToCheck] < target)
{
currSum = currSum + arr[nextIndToCheck];
nextIndToCheck++;
}
else
{
currSum = currSum - arr[startInd];
startInd++;
}
if(startInd == nextIndToCheck)
{
nextIndToCheck = startInd+1;
currSum = arr[nextIndToCheck];
}
}

return NO;
}

• Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. – Raphael Sep 24 '16 at 21:27
• You may be interested in our reference question. – Raphael Sep 24 '16 at 21:27