First Subarray Sums to Target


  • 2
    L

    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.
    

  • 1
    L

    @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};
    }

  • 0
    C

  • 1
    S

    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};
    }
    

  • 0
    L

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


  • 0
    P

    @litiansq89 said in First Subarray Sums to Target:

    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;
    

    }


  • 0
    W

    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];
    };


  • 0
    N
    This post is deleted!

Log in to reply
 

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