# Two solutions to 2-sum

I have written a solution for two sum problem in variation. first is simple with two loops and another one is one loop and hash map.

But I wonder why the simple solution is faster than the efficent solution

simple solution -

func TwoSum(arr []int, s int) [][]int {
var sum [][]int
for i := 0; i < len(arr); i++ {
for j := i + 1; j < len(arr); j++ {
if arr[i]+arr[j] == s {
sum = append(sum, []int{arr[i], arr[j]})
}
}
}
return sum
}


Hashmap solution -

func TwoSum1(nums []int, target int) [][]int {
var r = make([][]int, 0)
var m = make(map[int]int, 0)
for p, i := range nums {
j := target - i
if pos, ok := m[j]; ok {
if pos != p {
r = append(r, []int{j, i})
}
} else {
m[i] = p
}
}
return r
}


also, I have written Benchmark

type args struct {
arr []int
s   int
}

var tests = []struct {
name string
args args
want [][]int
}{
{
"One",
args{[]int{3, 5, 2, -4, 8, 11},
7,},
[][]int{{5, 2}, {-4, 11}},
},
}

func BenchmarkTwoSum(b *testing.B) {
for i := 0; i < b.N; i++ {
for _, tc := range tests{
TwoSum(tc.args.arr, tc.args.s)
}
}
}


BenchmarkTwoSum-4 3000000 382 ns/op

func BenchmarkTwoSum1(b *testing.B) {
for i := 0; i < b.N; i++ {
for _, tc := range tests{
TwoSum1(tc.args.arr, tc.args.s)
}
}
}


BenchmarkTwoSum1-4 2000000 561 ns/op

• Why don't you run the benchmark for exactly the same amount of operations? – Mast Jul 7 at 18:16
• What happens to the scores when you declare the variables outside of the function? Saves you from allocating memory a couple million times. – Mast Jul 7 at 18:39
• Asymptotic complexity tells you how the performance scales for large inputs. It tells you nothing about the comparative performance for small inputs. – 200_success Jul 7 at 19:28
• here is the link for more clarity https://coderbyte.com/algorithm/two-sum-problem – Manjeet Thakur Jul 8 at 10:59

Now in the case of this question, someone with a little more understanding of what's actually happening in Go might be able to tell you exactly what operation is making your hash map solution slower for those inputs. My guess... when you call make(map[int]int, 0) you are allocating space on the heap, which is likely taking a good amount of time.