i write a golang code to find two numbers that produce specific target number. I write the code using two for loops. Here is the code:

func FindTwoNumbers(arr []int, target int) {
    for i := 0; i < len(arr); i   {
        for j := 0; j < len(arr); j   {
            if arr[i] == arr[j] {
                continue
            }
            if arr[i] arr[j] == target {
                fmt.Printf("Numbers: %v and %v\n", arr[i], arr[j])
                arr = append(arr[:i], arr[i 1:]...)
                i--
            }

        }

    }
}

func main() {
    FindTwoNumbers([]int{1, 2, 3, 4, 5, 6, 7, 8, 9}, 14)
}

Here is the output:

go run main.go
Numbers: 5 and 9
Numbers: 6 and 8

Is there another way to write the code like maybe have less loop but produces the same result ?

CodePudding user response：

One approach you could use is to sort the array and then use two pointers, one at the beginning and one at the end, to find the pair of numbers that adds up to the target. This approach has a time complexity of O(n log n), due to the need to sort the array, but it may be faster in practice than the hash map solution.

As mentioned, another approach you could use is to create a hash map that stores the difference between the target number and each element in the array. Then, you can iterate through the array once, and check if the current element is present in the hash map. If it is, you have found a pair that adds up to the target number. Here is an example of how you could implement this approach:

func FindTwoNumbers(arr []int, target int) {
    differences := make(map[int]bool)
    for _, num := range arr {
        if differences[num] {
            fmt.Printf("Numbers: %v and %v\n", num, target-num)
        } else {
            differences[target-num] = true
        }
    }
}

This approach has a time complexity of O(n), which is a significant improvement over the O(n^2) time complexity of your original solution.

CodePudding user response：

Build a map that records how many times each value appears in the input slice; you can build such a map in linear time (wrt to the length of the input slice). Then, you can iterate over the resulting map, again in linear time, in order to find the two ints of interest (if any).

Here is a simple implementation (caveat: it doesn't check for integer underflow/overflow):

func FindTwoNumbers(ns []int, target int) (int, int, bool) {
    sizeHint := len(ns) // optimises for cases where all elements are distinct
    m := make(map[int]int, sizeHint)
    for _, n := range ns {
        m[n]  
    }
    for k, count := range m {
        diff := target - k
        if _, found := m[diff]; !found || diff == k && count < 2 {
            continue
        }
        return k, diff, true
    }
    return 0, 0, false
}

func main() {
    ns := []int{7, 8, 3, 4, 10}
    fmt.Println(FindTwoNumbers(ns, 14))
    fmt.Println(FindTwoNumbers(ns, 9))
}

(Playground)

Output:

4 10 true
0 0 false

CodePudding user response：

Oops. It looks like after I petitioned to re-open, I walked away and everyone else filled in an answer. For what it's worth:

func FindTwoNumbers(arr []int, target int) {

    table := make(map[int]int)

    // keep a map that maps each integer in the array to its number of occurrences
    for i := 0; i < len(arr); i   {
        table[arr[i]]  
    }

    // for each unique key, figure out what value it needs to be paired with
    // and check to see if that key is also in the map
    for key, _ := range table {
        var needed int = 1
        var match int = target - key
        if match == key {
            needed = 2 // if target is "6", then "3" needs to appear at least twice in the list
        }
        if key > match {
            continue // avoid reporting duplicate pairs by skipping when key>match
        }

        if table[match] >= needed {
            fmt.Printf("Numbers: %v and %v\n", key, match)
        }
    }
}

The above solution has a runtime of O(N).