如何优化Golang两数之和代码，用更少循环实现线性时间查找？

原实现代码 #

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)
}

原代码运行输出 #

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

优化实现方式 #

原双重循环的时间复杂度为O(n²)，可以通过以下两种方式降低时间复杂度，减少循环次数：

方法一：哈希表法（单次循环，时间复杂度O(n)） #

利用哈希表记录已遍历过的元素，每次遍历当前元素时，计算需要的补数（target - 当前元素），检查补数是否存在于哈希表中。这种方法仅需一次遍历，效率更高，同时通过额外的集合避免重复输出相同数对。

import "fmt"

func FindTwoNumbersWithMap(arr []int, target int) {
    seen := make(map[int]bool)
    outputPairs := make(map[string]bool)

    for _, num := range arr {
        complement := target - num
        if seen[complement] {
            // 统一数对排序格式，避免重复记录(5,9)和(9,5)
            var pairKey string
            if num < complement {
                pairKey = fmt.Sprintf("%d-%d", num, complement)
            } else {
                pairKey = fmt.Sprintf("%d-%d", complement, num)
            }
            if !outputPairs[pairKey] {
                fmt.Printf("Numbers: %v and %v\n", complement, num)
                outputPairs[pairKey] = true
            }
        }
        seen[num] = true
    }
}

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

运行输出与原代码一致：

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

方法二：双指针法（先排序，时间复杂度O(n log n)） #

先对数组排序，再用左右两个指针从数组两端向中间移动，根据两数之和与目标值的关系调整指针位置：

• 若和小于目标值，左指针右移
• 若和大于目标值，右指针左移
• 若等于目标值，记录结果并同时移动两个指针

import (
    "fmt"
    "sort"
)

func FindTwoNumbersWithTwoPointers(arr []int, target int) {
    // 复制原数组，避免修改原数据
    sortedArr := make([]int, len(arr))
    copy(sortedArr, arr)
    sort.Ints(sortedArr)

    left := 0
    right := len(sortedArr) - 1

    for left < right {
        sum := sortedArr[left] + sortedArr[right]
        if sum == target {
            fmt.Printf("Numbers: %v and %v\n", sortedArr[left], sortedArr[right])
            left++
            right--
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
}

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

运行输出同样一致：

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

内容的提问来源于stack exchange，提问作者purple hippo