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
}

复杂性分析

• 时间复杂度: ?(?)

  • 只需要一次遍历数组，使得 时间复杂度接近线性。

• 空间复杂度:o(n)

  • 哈希映射存储每个元素及其索引。

优点和缺点
优点：时间复杂度最有效的方法，具有干净、紧凑的实现。
缺点：无，因为它实现了该问题的最佳时间和空间复杂度。

以上是LeetCode 上的'二和问题”的详细内容。更多信息请关注PHP中文网其他相关文章！