Tuesday, December 2, 2014

Facebook: Subarray sums to the target value

http://www.geeksforgeeks.org/find-subarray-with-given-sum/

Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.
Examples:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found


Idea:
Sliding window, use two pointers, start and i. First accumulate A[i] with current sum so far. 
If current sum is greater than the target, we shrink the window by moving the start pointer steps forward and subtract the  A[start] from current sum, until the current sum is less than the target value again. Last we need to check if current sum is equal to the target. If yes, means we found one subarray of which the sum is equal to the target, and return true. 


Code (Java):
public class Solution {
    boolean subArraySumToTarget(int[] A, int target) {
        if (A == null || A.length == 0 || target < 0) {
            return false;
        }
        
        int curSum = 0;
        int start = 0;
        for (int i = 0; i < A.length; i++) {
            curSum += A[i];
            
            while (curSum > target) {
                curSum -= A[start];
                start++;
            }
            
            if (curSum == target) {
                return true;
            }
        }
        
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] A = new int[]{15, 2, 4, 8, 9, 5, 10, 23};
        int target = 5;
        System.out.println(sol.subArraySumToTarget(A, target));
    } 
}


Follow-up:
How about there are negative numbers in the array?

The idea is to use a hash table. For each A[i], we calculate the prefix sum, which is the sum of A[0] + ... + A[i] = X. We save the X + T into the hash table as the key. The value is the index i. If X + T is not in the hash table, we insert the key, value pair into the table. When we go to the point y, we calculate its prefix sum, and say it as Y. If Y is in the table, that means X + T = Y, i.e, Y - X = T. It means from i + 1 to j its sum equals to the target T. If Y is not in the hash table, add Y + T into the table. 

Code (Java):

import java.util.*;
public class Solution {
    public void subArraySum(int[] A, int target) {
        if (A == null || A.length == 0) {
            return;
        }
        
        int curSum = 0;
        Map map = new HashMap();
        
        for (int i = 0; i < A.length; i++) {
            curSum += A[i];
            if (curSum == target) {
                System.out.println("subset : 0 - " + i + " ");
            } else if (map.containsKey(curSum)) {
                System.out.println("subset : " + (map.get(curSum) + 1) + " - " + i);
                
                map.put(curSum, i);
            } else {
                map.put(curSum + target, i);
            }
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] A = new int[]{1,2,3,4,-9,6};
        int target = 6;

        sol.subArraySum(A, target);
    }
}








No comments:

Post a Comment