4Sum

Given an array S of n integers, are there elements abc, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
  • Elements in a quadruplet (a,b,c,d) must be in non-descending order.
  • The solution set must not contain duplicate quadruplets.
Solution: here I first generate an array with n(n-1)/2 elements storing the all possible two sums, and the corresponding indices.

Then use a hash map to store these indices. Note that the key (the two sums) is not unique! and   I don't know how to write the hash function if using pair<int, int> as a key...

Since the keys are not unique, multimap has to be used...

Comments

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs