Find two number from an unsorted array whose sum equal to a given number
Given an array [3, 5, 1] and sum = 8
Find two elements equal to the sum = 8
Naive solution, the runtime is $\mathcal{O}(n^2)$
Select every pair of elements and check whether the sum equals to the given number.
            for(int i=0; i < len; i++){
for(int j=0; j < len; j++){
if(i != j && array[i]*array[j] == sum){
print(array[i], array[j]);
}
}
}


Better solution $\mathcal{O}(n)$ with HashMap
Special case [4, 4, 4, 1, 7] sum = 8
This should be two pairs [4, 4, 7, 1]
// [4, 1, 7] 8
// {4, 7, 1}
// 4 -> 1
// 7 -> 1
// 1 -> 1
//
// [4, 4, 1, 7]
// {4, 4, 7, 1}
// 4->2
// 7->1
// 1->1
public static List<Integer> sum(Integer[] arr, int sum) {
List<Integer> list = new ArrayList<Integer>();
if(arr != null){
int len = arr.length;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(Integer n : arr){
if(map.containsKey(n)){
Integer v = map.get(n);
map.put(sum - n, v.intValue() + 1);
}else{
map.put(sum - n, 1);
}
}

for(Integer n : arr){
if(map.containsKey(n)){
Integer v = map.get(n);
if(v != null){
if(2*n == sum){
if(v.intValue() > 1){
if(v.intValue() % 2 == 1){
for(int i=0; i<v.intValue()-1; i++)
}else{
for(int i=0; i<v.intValue(); i++)
}
map.remove(n);
}
}else{