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
https://coderbyte.com/algorithm/two-sum-problem
\$\endgroup\$ – Manjeet Thakur Jul 8 at 10:59