2Sum

Given an array a of n integers find all possible Pythagorean triplets from the array. A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. this formula is derived from Pythagoras theorem: _“For every right angle triangle with side lengths a, b, and c=> a_2 + b2 = c2“. Solution: Conceptually it is similar to Find Non duplicate pairs that sum to S and 3 SUM problem [Read More]

Problem Statement: Problem Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.  Making more generic:  Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = T. Solution Brute force approach is of O(n^3) but we can solve it in O(n^2) by using the approach in 2 sum problem approach. [Read More]

how to build the hash table in the approach 3. als… Unknown - Feb 3, 2014how to build the hash table in the approach 3. also i think you should check if hash(T-arr[i]) is empty first. This comment has been removed by the author. Hi Jianchen, I think we can use hashmap or we can use element as an index in the array. I think only way hash() is empty when the given array is null or has no element. [Read More]

You are given an array of n integers and a target sum T. The goal is to determine whether or not there are two numbers x,y in A with x+y=T. Example : Suppose we have an int array = {5, 3, 7, 0, 1, 4, 2} and T = 5. The unique pairs that sum up to 5 are (5, 0) (3, 2) and (1, 4). There are three approaches to solve this problem - 1) brute force, 2) sort the array and use binary and search, and 3) Using the hashtable. [Read More]