凯里展示型网站设计,wordpress 免费主机,中级经济师考试题库1000题,东莞网站建设 胶粘包装材料原题链接#xff1a;1.两数之和
根据题意可以得出 需要找出数组nums内 有两个元素相加等于target的两个整数#xff0c;并且返回这两个证书的下标。并且数组内有重复元素#xff0c;但是返回的答案不能有重复元素出现
要记住的就是#xff0c;需要判断元素是否出现过1.两数之和
根据题意可以得出 需要找出数组nums内 有两个元素相加等于target的两个整数并且返回这两个证书的下标。并且数组内有重复元素但是返回的答案不能有重复元素出现
要记住的就是需要判断元素是否出现过或者是否在集合里存在就可以考虑用哈希法去做
使用什么方法为什么使用
可以使用hash法因为要根据值返回下标可以理解为根据key返回value键值对 所以也使用map又因为是需要查询在时间复杂度上就是用以哈希表为底层的unordered_map容器。 map主要用来去重 以及到时候返回需要查找的值相应的下标 本题中key用来存储需要的差值而value用来存储下标
思路 只需要遍历nums然后从nums[i]开始计算target - nums[i]得出差值 再到unordered_map中查询是否有需要的差值 如果没有则将numsi和i(下标)存入unordered_map 中等待下次查询 如果有则代表map-scond为需要的差值而i为差值的下标返回{map-scond,i }即可 map -scond 为该元素的值map -fast为该元素的键
代码
class Solution {
public:vectorint twoSum(vectorint nums, int target) {std::unordered_map int,int map;for(int i 0; i nums.size(); i){int s target - nums[i];auto item map.find(s);//存在返回元素的迭代器不存在则返回map.end()if(item map.end()){//差值不存在于map里面代表未出现过则将nums[i]的值和下标存入map中map.insert(pairint, int(nums[i],i));}else{//差值存在map里面return {item-second,i};}}return {};}
};
