# First Subarray Sums to Target

• Given a non-empty array `nums` contains positive integers and a positive integer `target`.
Find the first subarray in `nums` that sums up to `target` and return the begin and end index of this subarray. If there is no such subarray, return `[-1, -1]`.

For example:

``````input: nums=[4, 3, 5, 7, 8], target = 12
return: [0, 2]
explain: 4 + 3 + 5 = 12. Although 5 + 7 = 12, [4, 3, 5] is the first subarray that sums up to 12.

input: nums[1, 2, 3, 4], target = 15
return: [-1, -1]
explain: Thers is no such subarray that sums up to 15.
``````

• @litiansq89

static int[] subarray(int[] array, int start, int target){

``````	int sum=0;
int[] result = new int[2];
for(int i=start; i<array.length; i++)
{
sum +=array[i];
if(sum==target){
result[0]=start;
result[1]=i;
return result;
}else
if(sum>target)
return subarray(array, start+1, target);
}

return new int[] {-1,-1};
}``````

• This solution is O(n) run time.

``````private static int[] find(int[] a, int target) {
if (a.length < 2 || target < 0) {
return new int[]{-1,-1};
}
int start = 0, end = 1, n = a.length;
int runningSum = a[start] + a[end];
while (end < n) {
if (runningSum == target) {
return new int[]{start,end};
} else if (runningSum > target) {
runningSum -= a[start];
start++;
} else if (runningSum < target) {
end++;
if (end < n) {
runningSum += a[end];
}
}
}
return new int[]{-1,-1};
}
``````

• #include <stdio.h>
int main()
{}

• 4, 3, 5, 7, 8

#include <iostream>

using namespace std;

int * FindSol(int *arr, int n, int target){

``````int *res = new int[n];
int sum = 0;

for(int i=0; i<n; i++){
res[i] = -1;
}

// Sort
sort(arr, arr + n);

// Calculating sum
for(int i=0; i<n; i++){
sum += arr[i];
}

sum = target;
int i=0, j=0;
while(sum > 0 || i == n-1){
if(sum == 0){
break;
}

// At this point it is very clear that
// we have to move i to next element means
// cant take the first element as reference
// So resetting res and i and j.
if(sum <arr[i]){
sum = target;
fill_n(res, n, -1);
j= 0;
i = i-1;
}

sum = sum - arr[i];
res[j] = i;
i++;
j++;
}

return res;
``````

}

int main(){

``````int arr[] = {4, 3, 5, 7, 8};
int target = 12;

int *res = FindSol(arr, 5, target);

for(int i=0; i<5; i++){
if(res[i] == -1){
break;
}
cout << arr[res[i]] << "\t";
}

return 1;
``````

}

• var SubarraySum = function(nums, n) {
let t = 0;
let s = -1;
let e = -1;
for(let j=0; j<nums.length; j++){
t = 0;
for(let i=j; i<nums.length; i++) {
t = t + nums[i];
if( t == n) {
s = j;
e = i;
break;
}
else if( t > n){
break;
}
}
if(s != -1 && e != -1)
break;
}
return [s, e];
};

• This post is deleted!

• Some ideas for a O(n) solution:
Let

``````f[-1] = 0
f[i] = nums[0] + ... + nums[i]
``````

Then the answer [i,j] must satisfy

``````f[j] - f[i - 1] == target  <1>
``````

So now the problem can be solved by finding out the min i, j which satisfy <1>

``````HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1)
int f = 0;
for (int i = 0; i < nums.length; ++i){
f += nums[i];
if (map.containsKey(target - f)){
int[] sol = new int[2];
sol[0] = map.get(target - f) + 1;
sol[1] = i;
return sol;
}
map.put(f, i);
}
int[] sol = new int[2];
sol[0] = -1;
sol[1] = -1;
return sol;
``````

• public static int[] subarray(int[]nums,int target){
int[]res=new int[2];
int start=0;
int end=0;
int sum=0;
for(start=0;start<nums.length;){
while(end<nums.length && sum<target){
sum+=nums[end];
end++;
}
if(sum==target){
res[0]=start;
res[1]=end-1;
System.out.println(""+res[0]+" "+res[1]);
return res;
}
else {
sum-=nums[start];
start++;
}
}
if(start>=nums.length){
res[0]=res[1]=-1;
}

``````	return res;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.