当前位置：首页 > news >正文

20241105，LeetCode 每日一题，用 Go 实现两数之和的非暴力解法

news 2024/11/5 19:10:34

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。  你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。  你可以按任意顺序返回答案。  示例 1：  输入：nums = [2,7,11,15], target = 9  
输出：[0,1]  
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。  
示例 2：  输入：nums = [3,2,4], target = 6  
输出：[1,2]  
示例 3：  输入：nums = [3,3], target = 6  
输出：[0,1]  提示：  2 <= nums.length <= 104  
-109 <= nums[i] <= 109  
-109 <= target <= 109  
只会存在一个有效答案

思路

1、使用 Hash 表（Go 语言中是 map 类型）存储遍历过程中的数组元素和下标，从而避免使用 for for 两层循环的暴力解法，将时间复杂度从O(N^2)降低到O(N)。

2、指定 Hash 表的初始容量，避免运行中的内存重新分配。

解题过程

1、初始化一个空的哈希表 hashMap 来存储遍历过的数字及其索引。

2、遍历数组 nums，对于每个元素 nums[i]：

计算 target-v，得到与当前元素配对的目标数字。
检查这个目标数字是否已经在 hashMap 中存在：
- 如果存在，说明找到了一对数字，它们的和等于目标值，返回它们的索引。
- 如果不存在，将当前元素及其索引存入 hashMap。

3、如果遍历结束后没有找到任何一对数字，返回 nil。

复杂度

时间复杂度: O(n)
空间复杂度: O(n)

Code

func toSum(nums []int, target int) []int {  hashMap := make(map[int]int, len(nums))  for k, v := range nums {  if p, ok := hashMap[target-v]; ok {  return []int{p, k}  }  hashMap[v] = k  }  return nil  
}