首页 > > 程序设计 > C/C++ >

leetcode第一题两数之和击败了 98.11% 的用户的…

2019-11-15 16:01:17来源：博客园阅读 ()

leetcode第一题两数之和击败了 98.11% 的用户的答案（C++）

虽然题目简单，但我这好不容易优化到前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 };