/* Impliment a method that will determine if there exists a range of non-negative elements in an array that sum up to a specific non-negative number

    Example 1 - targetSum = 3, numbers = [1, 7, 1, 1 ,1, 5, 6, 1] - output true (the sum of the elemtns in range 2 to 4 is 3)
    Example 2 - targetSum = 7, numbers = [0, 4, 5, 1, 8, 9, 12, 3, 1] - output false (no range sums to 7)
*/

using System;

namespace Solution {
    class MainClass {
        public static void Main(string[] args) {
            /* Note: this implementation also accounts for these edge cases:
             *       target = 10, arr = { 1, 1, 1, 1 }
             *       target =  4, arr = { 10, 9, 8, 6, 5, 4 }
             */
             
            int[] arr = { 1, 7, 1, 1 ,1, 5, 6, 1 };
            int target = 3;
            Console.WriteLine(ContainsSubArray(arr, target));
        }

        private static bool ContainsSubArray(int[] arr, int target) {
            int startIndex = 0, endIndex = 0;
            int tmpSum = arr[0];

            while (endIndex < arr.Length) {
                if (tmpSum == target) {
                    return true;
                }
                else if (tmpSum > target) {
                    tmpSum -= arr[startIndex++];
                }
                else if (++endIndex < arr.Length) {
                    tmpSum += arr[endIndex];
                }
            }

            return false;
        }
    }
}