1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
/* 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;
}
}
}
|
