Given an array, find all the pairs of elements whose sum is k . Soln :: By Anton Lunyov (using STL map)

map.cpp

// http://discuss.codechef.com/questions/3292/algorithm-given-an-array-find-all-the-pairs-of-elements-whose-sum-is-k
/*For the original problem here is very simple O(N * log N) solution using STL map.

Put the array in map:  */

map < int, int > cnt;
for (int i = 0; i < n; ++i) {
   cnt[a[i]]++;
}

/*Then iterate over map and for the given value val add to the answer cnt[val] * cnt[k - val] if val < k - val and add cnt[val] * (cnt[val] - 1) / 2 if val == k - val, since from the set containing only elements k / 2 the number of pairs is the (cnt choose 2) number: */

long long ans = 0; // long long since for n up to 100000, the answer could not fit in int
for(auto &pair : cnt) // C++11 style
{
    val = pair.first;
    // use long long cast since this product can overflow
    if (val < k-val) {
        ans += (long long)cnt[val] * cnt[k - val];
    } else if (val == k-val)
        can += (long long)cnt[val] * (cnt[val] - 1) / 2;
}

/*ans is now the final answer.

The same can be made without map. You need to sort the array, create an array of pairs (val, cnt) like map from the previous solution, and then make the last loop either using binary search for finding k - val or using method if two pointers.

For the second problem you should clarify what is sub-array (contiguous or any sub-sequence), and what means find sub-array (just find any sub-array or with maximal size or find all such sub-arrays (their number)). */

Soln :: By Anton Lunyov (using STL map)

http://discuss.codechef.com/questions/3292/algorithm-given-an-array-find-all-the-pairs-of-elements-whose-sum-is-k