两数之和等于目标值 亦凉 2022-05-27 09:10 133阅读 0赞 ### 题目: ### 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数,将这两个数通过另一个数组返回。可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 **示例:** 给定 nums = \[2, 7, 11, 15\], target = 9 因为 nums\[0\] + nums\[1\] = 2 + 7 = 9,所以返回 \[0, 1\] #### 第一种方法: #### 使用两层for循环,如果两个数之和等于目标值,返回两个索引,这样可以把每一个数据都遍历到,但是时间复杂度为O(N^2)比较高。 代码实现: void TwoSum(vector<int>& v1, vector<int>& v2, int key) { for (int i = 0; i < v1.size(); i++) { for (int j = 0; j < v1.size(); j++) { if (v1[i] + v1[j] == key) { v2.push_back(i); v2.push_back(j); return; } } } } #### 第二种方法: #### 这种方法针对于有序的数组,如果数组重元素不是升序的,需要先将他排序。 第二种方法,我们是这样的,我们先创建两个索引begin和end,分别指向数组中最小的元素和最大的元素,将这两个数加起来,如果之和等于key,俺么直接返回这两个数据的索引;如果两数之和小于key,那么begin++;如果两数之和大于key,那么end–;这样循环,直至begin和end相遇。 代码实现: void TwoSum(vector<int>& v1, vector<int>& v2, int key)//这个必须是升序的 { int begin = 0; int end = v1.size() - 1; while (begin < end) { if (v1[begin] + v1[end] == key) { v2.push_back(begin); v2.push_back(end); return; } else if (v1[begin] + v1[end] < key) begin++; else end--; } } #### 第三种方法: #### 我们先创建一个unordered\_map,假设题目给的数组是v1,我们用key减去v1\[0\],如果得到的结果在map中,那说明我们找到了题目要求的两个数,如果得到的结果不在map中,我们把v1\[0\]和它的索引一起插入map中。循环下去,就可以得到结果了。 因为在哈希中查找的效率是O(1)是非常高的,这样我们就可以以较高的效率完成这道题了。 代码实现: void TwoSum(vector<int>& v1, vector<int>& v2, int key) { //哈希, 下标i作为value传入 unordered_map<int, int> m; for (int i = 0; i < v1.size(); i++) { unordered_map<int, int>::iterator it = m.find(key - v1[i]); //没找到返回end(),找到了返回数据对应的迭代器 if (it != m.end())//找到了 { v2.push_back(m[key - v1[i]]); v2.push_back(i); } else//没找到插入 m.insert({ v1[i], i }); } } 测试程序及运行结果: ![这里写图片描述][70] [70]: /images/20220527/30a59eaf847f45d798958fdde2106475.png
还没有评论,来说两句吧...