Subarray with sum 0 or k

Find if there is a sub-array with sum k

Method 1: Positive Numbers only: O(n)

Initialize a variable curr_sum as first element. curr_sum indicates the sum of current subarray. Start from the second element and add all elements one by one to the curr_sum. If curr_sum becomes equal to sum, then print the solution. If curr_sum exceeds the sum, then remove trailing elemnents while curr_sum is greater than sum.
http://www.programcreek.com/2014/05/leetcode-minimum-size-subarray-sum-java/

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

http://blog.gainlo.co/index.php/2016/06/01/subarray-with-given-sum/

Method 2: Negative Numbers also covered : Using Map: O(n)

An efficient way is to use a map. The idea is to maintain sum of elements encountered so far in a variable (say curr_sum). Let the given number is sum. Now for each element, we check if curr_sum – sum exists in the map or not. If we found it in the map that means, we have a subarray present with given sum, else we insert curr_sum into the map and proceed to next element. If all elements of the array are processed and we didn’t find any subarray with given sum, then subarray doesn’t exists.

http://www.geeksforgeeks.org/find-subarray-with-given-sum-in-array-of-integers/

Variation:1:Find if there is a subarray with 0 sum

Method 1:Hashing

We can also use hashing. The idea is to iterate through the array and for every element arr[i], calculate sum of elements form 0 to i (this can simply be done as sum += arr[i]). If the current sum has been seen before, then there is a zero sum array. Hashing is used to store the sum values, so that we can quickly store sum and find out whether the current sum is seen before or not.

http://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

http://www.geeksforgeeks.org/print-all-subarrays-with-0-sum/

Method 2:Recursion

#include<stdio.h>

#include<stdlib.h>

#define SIZE 9

int hasZero(int* A, int len, int prevSum)

{

    if(len == 1)

        return((A[0]+prevSum) == 0);

    int sum = prevSum + A[0];

    if(sum == 0)

        return 1;

    return hasZero(A+1, len-1, sum) | hasZero(A+1, len-1, 0);

}

int main()

{

    int A[SIZE] = {-2, 1, 4, -1, 6, -3, 3, -4, 7};

    printf("hasSum: %d\n", hasZero(A, SIZE, 0));

    getchar();

    return 0;

}

Variation:2

Find the largest subarray with 0 sum

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

Variation:3

Smallest subarray with sum greater than a given value

http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

Variation:4
Subarrays of size k that sum up to ssum.
Given an array, subarray size k and a number ssum,
find the number of subarrays of size k that sum up to ssum.
Also,Solve the above problem if the number of sub sequences are to be found given a sub
sequence sum of ssum in an array
Variation:5
Subarray with sum closest to zeroGiven an array contains positive and negative values, find the subarray, whose sum is most closed to zero. Require nlogn time complexity.