[leetcode_1]Two Sum

这个题目的意思是说，给一个数组numbers和一个target，求解是否能在numbers中找出两个数下标为index1和index2，这两个数的和是target。

值得注意的是，numbers的下标从1开始。但是vector作为内置数组其实下标是从0开始的。

由于才开始做leetcode上的题目，所以用着很不习惯和以前做的oj不大一样。

特别是vector以前完全没接触过，现在才深深地体会到自己是C++的蒟蒻。

链接上一个学习vector的博客：http://www.cnblogs.com/charley_yang/archive/2010/12/11/1903040.html

就当vector是数组就好~~~~

下面是解题代码和思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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;
    }
};

思路很简单，暴力求解即可。

一次ac，不过时间是32ms，这个方法我们姑且认为是o(n^2)的方法，能不能更加优化？

后来我想了下如果对vector排序:o(nlogn)

然后对每个数依次和target求差，这个差去二分查找，这样复杂度应该在o(nlogn)。时间应该更快的~~~~当然还需要考虑下标的保存问题。