题解 | #两数之和#
两数之和
http://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f
题意理解
找出数组中和等于目标值的两个数,输出它们的下标,注意先输出小的下标。输出结果存在且唯一。
方法一
题目要求两个数值对应的index,首先想到双指针的方法。
先对数组进行排序,注意在排序时,原先的index也要跟着数值一起交换位置,否则最后输出新的index是错误的。这就需要我们自己定义一个结构体,里面存放数值和对应的旧index。
两个指针(非数据结构的指针)i,j分别指向开头和结尾,如果number[i]+number[j]==target即得到答案。若和小于target,说明加数小了,i就右移;若和大于target,说明加数大了,j左移。每一个数只要扫一遍就可以了。
示意图如下:
证明算法不会错过解:
当i扫到number[i']的时候,不可能和j右侧的数值相加等于target。因为之前j位于j'(j'>j)的时候,指针i右移直到两数之和大于target时停止,此时i<i',所以number[i']+number[j']一定大于target。
具体代码如下:
class Solution { public: /** * * @param numbers int整型vector * @param target int整型 * @return int整型vector */ //定义结构体Num_index,把数值和原先的index都对应地存储起来 typedef struct { int number; int index; }Num_index; //需要自己写sort函数里面的比较方法,这里比较number的数值 static bool compare(Num_index a, Num_index b) { return (a.number < b.number); } vector<int> twoSum(vector<int>& numbers, int target) { //定义一个Num_index类型的数组,将数值及其原先的index存入 vector<Num_index> num_index; for (int i=0;i<numbers.size();i++) { Num_index x; x.number = numbers[i]; x.index = i; num_index.push_back(x); } sort(num_index.begin(), num_index.end(), compare); vector<int> ans; //排序后,从两端向中间搜索;当i>=j时搜索完毕。 int i=0,j=numbers.size()-1; while (i<j) { if (num_index[i].number+num_index[j].number == target) { //注意先输出原先index小的值 ans.push_back(min(num_index[i].index,num_index[j].index)+1); ans.push_back(max(num_index[i].index,num_index[j].index)+1); return (ans); break; } else if (num_index[i].number+num_index[j].number < target) { i++; } else j--; } return ans; } };
时间复杂度:快速。使用快速排序的时间为;双指针遍历时,每个数值只经过了一遍,为。
空间复杂度:。创建了一个结构体数组重新存储数值和对应的旧index。
方法二
当我们遍历到某个numbers[i]时,就要看target-numbers[i]是否在数组中。这本来是一个双重循环,需要O(n^2)的时间。
考虑使用哈希表来标记某个数是否存在于数组中,把双重循环改为并行的两次循环。先遍历一遍来建立哈希表mymap,哈希规则为mymap[numbers[i]] = i;再遍历一遍数组number,查看target-numbers[i]是否在哈希表中,注意两个加数不能重复。
哈希表示意图如下:
具体代码如下:
class Solution { public: /** * * @param numbers int整型vector * @param target int整型 * @return int整型vector */ vector<int> twoSum(vector<int>& numbers, int target) { unordered_map<int, int> mymap; //建立哈希表 for (int i=0;i<numbers.size();i++) { mymap[numbers[i]] = i; } vector<int> ans; for (int i=0;i<numbers.size();i++) { int d = target - numbers[i]; //先判断target与numbers[i]的差是否在hash中,其次还要判断是否重复了。 if (mymap.count(d)!=0 && mymap.at(d)!=i) { ans = {i+1, mymap.at(d)+1}; break; } } return ans; } };
时间复杂度:。建立哈希表和使用哈希表进行查找的时间都为。
空间复杂度:。建立一个哈希表需要的空间。