LeetCode 上的'二和问题”-Golang-PHP中文网

LeetCode 上的'二和问题”

Barbara Streisand

发布： 2024-11-16 15:30:03

原创

163 人浏览过

Two Sum Problem’ on LeetCode

问题描述
给定一个整数数组 nums 和一个整数目标，返回两个数字相加达到目标的索引。

Go 函数签名：
func TwoSum(nums []int, target int) []int
示例1：
输入：nums = [2,7,11,15]，目标 = 9
输出：[0,1]
解释：因为 nums[0] nums[1] == 9，所以我们返回 [0, 1].
示例2：

输入：nums = [3,2,4]，target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3]，目标= 6
输出：[0,1]
解决方案1：暴力法

解决方案 1：暴力破解方法（嵌套循环）
在这种方法中，您检查每对元素以查看它们的总和是否达到目标。这涉及到使用两个嵌套循环迭代数组。

代码

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

登录后复制

复杂性分析

解决方案 2：二次哈希表
该解决方案通过使用哈希映射在第一遍中存储每个元素的值和索引来改进暴力方法。在第二遍中，您检查哈希映射中是否存在补集（即 target - num）。

代码

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    // First pass: populate the map with each element's index
    for i, num := range nums {
        numMap[num] = i
    }
    // Second pass: check for the complement
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok && i != j {
            return []int{i, j}
        }
    }
    return nil
}

登录后复制

解决方案 3：一次性哈希表（最佳解决方案）

这种方法在一次传递中结合了插入和查找。当您迭代数组时，您：
检查哈希映射中是否存在补集（即 target - num）。
如果找到补集，则返回索引。
如果没有，则将当前元素及其索引添加到哈希映射中以供将来查找。
代码

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok {
            return []int{j, i}
        }
        numMap[num] = i
    }
    return nil
}

登录后复制

复杂性分析