虽然题目简单,但我这好不容易优化到前2%,感觉也值得分享给大家(方法比较偷机)
题目:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
来源:力扣(leetcode)
链接:https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
我的解答:
1 class solution { 2 public: 3 vector<int> twosum(vector<int>& nums, int target) { 4 vector<int> res(2); 5 int endpos = nums.size(); 6 //vector内存是连续的 这里直接取地址 7 //这样后面访问时不需要调用vecotr的成员函数 8 //因为不清楚编译器优化级别 9 int *numarr = &nums[0]; 10 11 if (endpos < 5) 12 { 13 //数组长度比较小时使用原始的双循环法更快点 14 for (int i = 0; i < endpos; ++i) 15 { 16 //遍历数组,找出每个元素与target之差做为寻找目标 17 int nneed = target - numarr[i]; 18 for (int j = i + 1; j < endpos; ++j) 19 { 20 //在后面找,看有没有与目标相同的数字 21 if (numarr[j] == nneed) 22 { 23 //如果有直接返回 24 res[0] = i; 25 res[1] = j; 26 return res; 27 } 28 } 29 } 30 } 31 32 //数组比较大时使用一次遍历哈希查找的方法比较快 33 map<int, int> mpnums; 34 pair<map<int, int>::iterator, bool> pairret; 35 //int numcurr; 36 37 //遍历数组 38 for (int i = 0; i < endpos; ++i) 39 { 40 //把当前数值当key,当前位置当value插入map 41 //numcurr = numarr[i]; //实验发现这里使用numcurr取值代替numarr[i]反而慢了 42 //看来读取消耗远低于写 43 pairret = mpnums.insert(make_pair(numarr[i], i)); 44 45 //如果插入成功(大部分情况下是插入成功的) 46 if (pairret.second) 47 { 48 //查看map里面是否有目前值-当前元素值的数据存在 49 //如果有就说明找到目标 50 int numneed = target - numarr[i]; 51 map<int, int>::iterator it = mpnums.find(numneed); 52 if (it != mpnums.end() && it->second != i) 53 { 54 //题目要求不能重复使用自己,所以需要限制it->second != i 55 res[0] = it->second; 56 res[1] = i; 57 return res; 58 } 59 } 60 else 61 { 62 //如果插入失败说明 63 //已经在map存在相同数值,则看它们加起来是否等于target 64 if ((numarr[i] << 1) == target) //2 * numarr[i] 65 { 66 res[0] = pairret.first->second; 67 res[1] = i; 68 return res; 69 } 70 } 71 } 72 73 res.clear(); 74 return res; 75 } 76 77 };
执行结果:
通过
显示详情
执行用时 :8 ms, 在所有 cpp 提交中击败了98.11%的用户
内存消耗 :10.1 mb, 在所有 cpp 提交中击败了37.46%的用户
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/600960.html