两数之和解析
题目:
给定一个整数数组 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]
这个问题要求你设计一个高效的算法来找到数组中两个数,使得它们的和等于一个给定的目标值。
这要求你能够分析问题的本质,并设计出合适的解决方案。
这个问题的本质是搜索与匹配的问题,更具体地说,是在无序数组中查找满足特定条件(和为目标值)的两个数。
暴力解法1
最直接的方法是使用两层嵌套循环遍历数组,对于每对元素,检查它们的和是否等于目标值。这种方法的时间复杂度是O(n^2),其中n是数组的长度,对于大数据集来说效率很低。
func twoSum1(nums []int, target int) []int {for i := 0; i < len(nums); i++ {for j := 0; j < len(nums); j++ {if i == j { // 因为题目中不能使用两次相同的元素continue}if nums[i]+nums[j] == target {return []int{i, j}}}}return nil
}
我们仔细观察下这个两层循环,会发现有重复的比较。
当i=0时,nums[0]=2,2和5、9、4、11进行相加。
当i=1时,nums[1]=5,5和2、9、4、11进行相加。
可以发现nums[1]=5和2相加,已经被计算过了。
当i=2时,nums[2]=9,9和2、5、4、11进行相加。
可以发现nums[2]=9和2、5相加,已经被计算过了。
当i=3时,nums[3]=4,4和2、5、9、11进行相加。
可以发现nums[3]=4和2、5、9相加,已经被计算过了。
下面进行优化,减少重复计算。
暴力解法2
第二层循环从j开始(j>=i+1)
func twoSum2(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
}
哈希法1:
target=6,当num=2,需要在数组中找出6-2=4,这种查找,哈希最擅长,时间复杂度还是O(1)。
比较常规的方法,先把整个数组建立一个hash表,然后进行查找。
func twoSum3(nums []int, target int) []int {// key:数值,value:下标hashTable := make(map[int]int, 0)for i, num := range nums {hashTable[num] = i}for i := 0; i < len(nums); i++ {if v, ok := hashTable[target-nums[i]]; ok {return []int{i, v}}}return nil
}
哈希法2:
上一个哈希法,可以优化为不提前建立哈希表,在循环的过程中建立哈希。
func twoSum4(nums []int, target int) []int {// key:数值,value:下标nummap := make(map[int]int, 0)for i := 0; i < len(nums); i++ {if v, ok := nummap[target-nums[i]]; ok {return []int{v, i}} else {nummap[nums[i]] = i}}return nil
}
总结:
这个问题的本质是搜索。更具体地说,是在无序或有序数组中查找满足特定条件(和为目标值)的两个数。
这个问题通常可以通过以下几种方式解决,每种方式都体现了不同的算法思想和技巧:
暴力法(Brute Force)
//最直接的方法是使用两层嵌套循环遍历数组,对于每对元素,检查它们的和是否等于目标值。这种方法的时间复杂度是O(n^2),其中n是数组的长度,对于大数据集来说效率很低。
哈希表(Hash Table)
更高效的方法是使用哈希表来记录遍历过的元素和它们的索引。遍历数组时,对于每个元素,我们检查目标值减去当前元素的结果是否已经在哈希表中。如果在,说明我们找到了满足条件的两个数;如果不在,将当前元素及其索引添加到哈希表中。这种方法的时间复杂度是O(n),其中n是数组的长度,因为它只需要遍历数组一次。
双指针法(Two Pointers)
(当数组有序时):如果数组是有序的,我们可以使用双指针法。一个指针从头开始,另一个指针从尾开始。根据两个指针所指向元素的和与目标值的大小关系,移动较小的那个指针(如果和小于目标值,移动头指针;如果和大于目标值,移动尾指针)。这种方法的时间复杂度也是O(n),但它要求数组必须是有序的。
思考题
如果 nums 是有序的,是否还需要哈希表?
如果要求寻找三个数,它们的和等于 target 呢?