网站推广目标,网站开发属于固定资产吗,国家企业信息信用信息系统查询,好好建站题目
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案#xff0c;并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。 …题目
给定一个整数数组 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
}运行结果 引用https://leetcode.cn/problems/two-sum/solutions/2976507/goyu-yan-liang-shu-zhi-he-ti-jie-by-deng-pp8x
