# Two Sum (a+b =s) Problem

By | May 23, 2014

The Two Sum problem is like this :

Given an array of integers A, find two numbers a,b such that they add up to a specific target number s.
a+b =s

Though this problem looks simple but this problem forms a kind of base for solving other bigger problems like 3sum problem and 4 sum problem . So I advice the users to think on this problem carefully and see what all solutions can be there .

Ex Input : A={4,5,1,2,3} s=8
output :5,3

We can take different approaches to solve this problem .

Here’s the Naive Approach using two for loops trying all possible sums of two numbers .The complexity of this solution is O(n^2).

Approach 2 :
Here’s another way of solving this problem using HashMaps.
Algorithm:

• Iterate through the array
• for each element A[i] is the array check if ther’s an element s-A[i] present in the map
• if yes return A[i] and s-A[i]
• else add A[i] to map and continue

Here’s the code . It run’s in O(n) time and requires O(n) space .

Approach 3 :
Though the above approach works good . But requires extra space for storing the hash table . Some interviewwers won’t allow you to do that . Here’s another algorithm to solve two sum problem in O(nlgn) without using extra space.
Algorithm

• Sort the array A
• Initiale two pointers head =0 and tail= A.length