一、两数之和(简)
题目
给定一个整数数组 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 <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案
题解
当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到哈希法。
数组可以做哈希表,set也可以,map也可以,用哪个呢
对于这道题,不仅要知道元素有没有遍历过,还有知道这个元素对应的下标。需要使用key-value结构来存放,key来存元素,value来存下标,那么使用map正合适
而C++中map有三种类型,如下所示:
映射 | 底层实现 | 是否有序 | key的数量 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::map | 红黑树 | key有序 | 只能有一个key | key不可修改 | O(log n) | O(log n) |
std::multimap | 红黑树 | key有序 | 可以有多个key | key不可修改 | O(log n) | O(log n) |
std::map | 哈希表 | key无序 | 只能有一个key | key不可修改 | O(1) | O(1) |
这道题目中并不需要key有序,所以选择std::unordered_map效率更高
接下来就很简单了,首先把数组中的元素作为key,value用来存下标;
我们只需要查找map中是否存在target-nums[i]
的值,没有就将(nums[i],i)
加入map,继续遍历即可
1 | class Solution { |
二、三数之和(中)
题目
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。
请你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
提示:
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
题解
这道题只用求值,不用求下标,就不需要用哈希表了,用双指针就是最方便的。
从小到大排序后,就可以用双指针了
因为有需要三个数,可以固定一个数a,双指针遍历剩下的数组,求双指针之和target为0-a
即可
left为数组头,right为数组尾,大于target则right--
,小于target则left++
主要是去重,因为有可能数组中同一个数字出现多次,排完序后,相同的数字会连在一起,只要将当前的值和前一个值比就可以去重了。
1 | class Solution { |
三、最接近的三数之和(中)
题目
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2:
输入:nums = [0,0,0], target = 1
输出:0
提示:
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10^4 <= target <= 10^4
题解
和三数之和非常类似,求与target最接近的三元组,即差值的绝对值最小。
和三数之和一样,从小到大排序后,固定一个数a,求双指针之和尽可能接近target-a
即可
如果a+b+c>target
,right--
;如果a+b+c<target
,left++
,同时和三数之和一样需要去重,只是增加一步,在和taget比较之前,需要先update一下三数之和,记录下最接近target的值。
1 | class Solution { |