题目:
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那两个整数, 并返回它们的数组下标。
题目分析:
数组中找到两个数相加的值为指定的某个值。这两个数一定为一对。
解题:
解法1:
使用暴力的方法,target减去数组中的整数,然后与其他整数去判断。这样就是一个双层循环。第一层循环target- nums[i]得到值X,然后第二层去循环数组寻找等于X的下表。第一层时间复杂度N,第二层时间复杂度N,两者具 有关联最终时间复杂度:N^2。空间复杂度O(1)
解法2:
对于暴力循环的方法,我们第一层target - nums[i]得到值X,依旧保留,但是第二层时,如果我们把数组放入 hash中,那么X只需判断一次O(1)。相对于每个X都要和数组其他数进行判断时间复杂度降低很多O(N)。这样就 有一个问题,何时将数组元素写入hash呢?这时借助题目分析中两个数一定是一对,我们可以在判断X等于数组 值时,如果不相等就写入hash,相等就是我们要的结果。
func twoSum(nums []int, target int) []int { hashtable := make(map[int]int,len(nums)) for i,j := range nums{ if v,ok := hashtable[target - j] ;ok{ return []int{i,v} } hashtable[j] = i } return nil }
题目链接:https://leetcode-cn.com/problems/two-sum