betandr · February 11, 2022 15:48 · Feb 11, 2022
diff --git a/indices.go b/indices.go
@@ -0,0 +1,96 @@
+// Given  an array  of integers that is already sorted in ascending
+// order find two numbers such that they add up to a specific target number.
+//
+// The function twoSum should return indices of the two numbers such that
+// they add up to the target where index1 must be less than index2.
+package main
+
+import (
+	"errors"
+	"fmt"
+	"time"
+)
+
+// Loop through the slice and then loop through each other possibility
+// Very inefficient as worst case is O(n2)
+func twoSumBruteForce(numbers []int, target int) (int, int, error) {
+
+	for i := 0; i < len(numbers); i++ {
+		for j := i; j < len(numbers); j++ {
+			if numbers[i]+numbers[j] == target {
+				return i, j, nil
+			}
+			// If the number is now higher than the target
+			// then we can just stop looking
+			if numbers[i]+numbers[j] > target {
+				break
+			}
+		}
+	}
+	return -1, -1, errors.New("no possible solution")
+}
+
+// Use two pointers to move together to find a solution linearly
+// More efficient as worst case is O(n)
+func twoSumPointers(numbers []int, target int) (int, int, error) {
+	p1 := 0
+	p2 := len(numbers) - 1
+
+	for p1 < p2 { // loop until collision
+		current := numbers[p1] + numbers[p2]
+
+		if current == target {
+			return p1, p2, nil
+		} else if current > target {
+			p2--
+		} else if current < target {
+			p1++
+		}
+	}
+
+	// This should never happen if a solution is guaranteed.
+	return -1, -1, errors.New("no possible solution")
+}
+
+func main() {
+	numbers := []int{2, 7, 11, 15}
+	target := 90
+
+	start := time.Now()
+	x, y, err := twoSumBruteForce(numbers, target)
+	elapsed := time.Since(start)
+	if err != nil {
+		fmt.Printf("BF [%s]: %s\n", elapsed, err)
+	} else {
+		fmt.Printf("numbers = %v, target = %d\n", numbers, target)
+		fmt.Printf(
+			"BF [%s]: The sum of %d and %d is %d. Therefore index1 = %d, index2 = %d.\n",
+			elapsed,
+			numbers[x],
+			numbers[y],
+			target,
+			x+1,
+			y+1,
+		)
+	}
+
+	start = time.Now()
+	x, y, err = twoSumPointers(numbers, target)
+	elapsed = time.Since(start)
+	if err != nil {
+		fmt.Printf("P [%s]: %s\n", elapsed, err)
+	} else {
+
+		fmt.Printf("numbers = %v, target = %d\n", numbers, target)
+		fmt.Printf(
+			"P [%s]: The sum of %d and %d is %d. Therefore index1 = %d, index2 = %d.\n",
+			elapsed,
+			numbers[x],
+			numbers[y],
+			target,
+			x+1,
+			y+1,
+		)
+	}
+
+}