TwoSum - Solutions: Naive O(n2), Sorted O(nlogn), Hash O(n)

TwoSum.ahk

/*
                 _____                __                 
                /__   \__      _____ / _\_   _ _ __ ___  
                  / /\/\ \ /\ / / _ \\ \| | | | '_ ` _ \ 
                 / /    \ V  V / (_) |\ \ |_| | | | | | |
                 \/      \_/\_/ \___/\__/\__,_|_| |_| |_|
                            Coded by errorseven @ 1/26/17

The two sum problem is a common interview question, and it is a variation of the
subset sum problem. There is a popular dynamic programming solution for the 
subset sum problem, but for the two sum problem we can actually write an 
algorithm that runs in O(n) time. The challenge is to find all the pairs of two 
integers in an unsorted array that sum up to a given S. 

For example, 
    if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should 
             return [[11, -4], [2, 5]] 
            because 11 + -4 = 7 and 2 + 5 = 7.

Naive solution

A naive approach to this problem would be to loop through each number and then 
loop again through the array looking for a pair that sums to S. The running time
for the below solution would be O(n2) because in the worst case we are looping 
through the array twice to find a pair.

*/

#Include ExtObj.ahk ; goo.gl/25zoCM

sum := 7
list := [3, 5, 2, -4, 8, 11]

MsgBox % twoSum(list, sum).print

/*
twoSum(arr, sum) { ; Naive O(n2)
    container := []
    while(i<arr.length()) {
        i:=A_Index, j:=i + 1
	while(j<=arr.length()) {
	    if(arr[i] + arr[j] == sum)
	    	container.push([arr[i], arr[j]])
	    j++
    	}
    }
    return container.length() ? container : false
}

/*
twoSum(arr, sum) { ; Sorted O(nlogn)
    container := [], low:=1, high:=arr.length()
    
    ; Sort the array
    arr:=arr.sort("N")
	
    While (low < high) {
		if (arr[low] + arr[high] == sum) {
                container.push([arr[low], arr[high]])
        }
        (arr[low] + arr[high] < sum) ? low++ : high--
    }
    return container.length() ? container : false      
}

*/

twoSum(arr, sum) { ; Hash O(n)
	obj := {}
	container := []
	
	for i, v in arr {
	    key := sum - v
            if(obj[key])
	        container.push([key, v])
	    obj[(v)] := i 
	}
	return container.length() ? container : false
}