Find subarray with given sum

Zero sum problem

• http://www.geeksforgeeks.org/find-the-largest-subarray-with-0-sum/

Given an array of integers, find length of the largest subarray with sum equals to 0.

Tag: hash table

Solution

The variable sum keeps track of the sum of the very first element to the current element.

So, the sum of A[i..j] = sum[j] - sum[i-1].

Since we want to find the zero sum, then A[i..j] must equal to zero, where sum[j] == sum[i - 1] .

The distance between i..j is j - i + 1, which then becomes the current index - the index stored in the map.

/**
 * http://www.geeksforgeeks.org/find-the-largest-subarray-with-0-sum/
 * Time complexity O(n)
 */
public class MaxiumnSubarrayWithZeroSum {
    public int maxLen(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int sum = 0;
        int maxLength = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];

            // handle special case when we meet a single element is 0
            if (nums[i] == 0 && maxLength == 0)
                maxLength = 1;

            // since we know the largest possible value if from 0-i 
            if (sum == 0)
                maxLength = i + 1;

            if (map.containsKey(sum)) {
                maxLength = Math.max(maxLength, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }

        return maxLength;
    }
}

Find subarray with given sum

Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

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

* Returns true if the there is a subarray of arr[] with sum equal to 'sum'
   otherwise returns false.  Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of first element
       and starting point as 0 */
    int curr_sum = arr[0], start = 0, i;

    /* Add elements one by one to curr_sum and if the curr_sum exceeds the
       sum, then remove starting element */
    for (i = 1; i <= n; i++)
    {
        // If curr_sum exceeds the sum, then remove the starting elements
        while (curr_sum > sum && start < i-1)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }

        // If curr_sum becomes equal to sum, then return true
        if (curr_sum == sum)
        {
            printf ("Sum found between indexes %d and %d", start, i-1);
            return 1;
        }

        // Add this element to curr_sum
        if (i < n)
          curr_sum = curr_sum + arr[i];
    }

    // If we reach here, then no subarray
    printf("No subarray found");
    return 0;
}