0
$\begingroup$

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;
}
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Sep 24 '16 at 21:27
  • 1
    $\begingroup$ You may be interested in our reference question. $\endgroup$ – Raphael Sep 24 '16 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.