asp.net 发布网站 ftp,做英文的小说网站有哪些,怎样做网站推销产品,关于营销的最新的新闻1、题目 给定一个整数数组 nums 和一个目标值 target#xff0c;请你在该数组中找出和为目标值的那 两个 整数#xff0c;并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一个元素不能使用两遍。 2、思考分析
双for循环的时间复杂度…1、题目 给定一个整数数组 nums 和一个目标值 target请你在该数组中找出和为目标值的那 两个 整数并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素不能使用两遍。 2、思考分析
双for循环的时间复杂度O(n^2)而哈希法的时间复杂度为O(1),所以哈希法显然更有效。 这里我们使用map而不使用set、或者自构造数组。 数组与set的局限 1、数组大小受到限制如果元素较少而哈希值太大会造成内存空间浪费 2、set是一个集合里面放的元素只能是一个key不能知道key所在的位置也就是说我们只能知道key是否存在。 而这一题不经要判断y是否存在还要疾苦y的下标。 3、使用map可以同时保存key、value类似于数组。我们可以用key保存数值用value保存数值所在下标。 C中map的有关用法可以参考这篇笔记:STL容器及其简单应用 这里我们选择unordered_map; 需要注意map.insert函数的用法;
map.insert(pairint, int (nums[i], i));3、哈希法
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int n nums.size();unordered_mapint,int map;for(int i0;in;i){auto iter map.find(target-nums[i]); //观察是否找到另外一个数//如果找到了if(iter !map.end()){//iter.first:key iter.second:下标return {i,iter-second};}map.insert(pairint, int (nums[i], i));}return {};}
};
