每日一题：Leetcode 1.两数之和

怼烎@ 2023-07-06 13:08 4阅读 0赞

## 题目描述： ##

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

**示例:**

给定 nums = \[2, 7, 11, 15\], target = 9

因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
所以返回 \[0, 1\]

## 题解： ##

**题目难度**：简单  
**解题思路**：  
在因疫情导致全国高校延迟开学的某一天，张小胖同学宅在家实在闲得没事干，于是他打开了尘封已久的Leetcode，准备刷他个天翻地覆。  
小胖看了一眼第一题“两数之和”的题目内容，不禁轻蔑一笑：“这题有何难？我只需要列举出数组中所有的两两组合（使用两层循环遍历数组），判断它们之和是否为给定值，即可轻松AC！”于是，他稀里哗啦一顿乱敲：

//方法一：暴力遍历法，时间复杂度O（n^2）
    func twoSum(nums []int, target int) []int { 
    	for i := 0 ; i < len(nums) ; i ++ { 
    		for j := i ; j < len(nums) ;j ++ { 
    			if nums[i] + nums[j] == target{ 
    				res := []int { i , j}
    				return res
    			}
    		}
    	}
    	return nil
    }

果不其然一发AC，小胖同学不禁非常得意。突然，一道奇异的光芒刺瞎了小胖的狗眼。

![在这里插入图片描述][20200219000029676.png]  
居然只击败了28.76%的用户，这对于追求速度的小胖同学来说，可谓出师不利，他不禁十分沮丧。不过他仔细一想，自己刚才使用了两层循环来列举不同的两两组合，这一做法无疑导致了大量的时间消耗在循环之中。那么，可不可以只使用一层循环就能找出加和为给定值的两个元素呢？换句话来说，可不可以在遍历数组的时候，一边遍历，一边判断之前遍历过的元素之中存不存在与当前元素之和为给定值的元素呢？  
答案当然是肯定的！  
只见他自言自语道：“我既然想遍历数组的时候对完成条件与否进行判断，那么我就需要实时刻刻查找之前遍历过的元素中是否存在可以与之匹配的元素，那么我就需要一个哈希表（HashMap）存储之前遍历过的元素下标（Key）和数据值（Value）。可是，我怎么对哈希表中是否存在能与之匹配的Value进行判断查找呢？”小胖不禁陷入沉思。  
突然，他灵光一现：“可以用逆向思维来解决！我可以逆用哈希表来存储之前的元素数据值（Key）与下标（Value），并计算当前元素数据值和给定值的差值dif。那么，我只需要判断哈希表中Key值为dif所对应的Value是否存在，就能实现对条件“两数之和”的判断了！”想到这里，张小胖顿时茅塞顿开，拿起键盘，又是哗哗一顿乱敲：

//方法2：哈希表法，时间复杂度O（n）
    func twoSum(nums []int, target int) []int { 
    	map1 := make(map[int]int)
    	for i := 0; i < len(nums); i++ { 
    		dif := target - nums[i]
    		x, j := map1[dif]
    		if j != false { 
    			return []int{ x, i}
    		}
    		map1[nums[i]] = i
    	}
    	return nil
    }

提交完毕，小胖看了一眼数据，顿时又喜又气：  
![在这里插入图片描述][20200219004215322.png]  
速度上去了，可由于使用了哈希表，使得空间复杂度从之前的O（1）直接升到了O（n），占用了较多的存储单元。不过，他转念一想：“万物有得必有失，人生又何尝不是一样？我们如果对结果过分苛求完美，又怎能收获这其中过程的点滴喜悦？”想到这里，张小胖同学顿时豁然开朗，便继续投入到了Leetcode的汪洋大海之中。

**原题目链接**：https://leetcode-cn.com/problems/two-sum/

[20200219000029676.png]: https://img-blog.csdnimg.cn/20200219000029676.png
[20200219004215322.png]: https://img-blog.csdnimg.cn/20200219004215322.png