这个题目的意思是说,给一个数组numbers和一个target,求解是否能在numbers中找出两个数下标为index1和index2,这两个数的和是target。
值得注意的是,numbers的下标从1开始。但是vertor作为内置数组其实下标是从0开始的。
由于才开始做leetcode上的题目,所以用着很不习惯和以前做的oj不大一样。
特别是vector以前完全没接触过,现在才深深地体会到自己是C++的蒟蒻。
链接上一个学习vector的博客:http://www.cnblogs.com/charley_yang/archive/2010/12/11/1903040.html
就当vector是数组就好~~~~
下面是解题代码和思路:
class Solution { public: vector<int> twoSum(vector<int> &numbers, int target) { // Note: The Solution object is instantiated only once and is reused by each test case. vector<int> answer(2); for(int i = 0;i < numbers.size();i++) { int flag = false; for(int j = 0;j < numbers.size();j++) { if(i != j && numbers[i] + numbers[j] == target) { answer[0] = i+1; answer[1] = j+1; flag = true; break; } } if(flag == true)break; } return answer;</p> <pre><code>} </code></pre> <p>};
思路很简单,暴力求解即可。
一次ac,不过时间是32ms,这个方法我们姑且认为是o(n^2)的方法,能不能更加优化?
后来我想了下如果对vector排序:o(nlogn)
然后对每个数依次和target求差,这个差去二分查找,这样复杂度应该在o(nlogn)。时间应该更快的~~~~当然还需要考虑下标的保存问题。