LeetCode[Day 1] Two Sum 题解

Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

---

思路

最近刚好开始看算法导论，里面有一道习题和这题非常类似，也是求解一串数组中是否存在两个数其和为一个给定值的问题。书上给出的答案复杂度是O(nlogn)，提示是对这串数排序。这样比暴力解O(n^2)的算法确实优化了不少。但是对于O(nlogn)的算法上，我觉得我还是有所偏差的。

我的想法还是比较自然的，排序之后，对每一个元素numbers[i]枚举，判断这串数中有没有一个数

numbers[j] = target-numbers[i]

当然，这里寻找numbers[j]这个数的时候，因为运用数组已经排序过后的性质进行二分查找，不然和暴力求解的复杂度就一样了。

看了一些其他人的题解之后，真是恍然大悟。原来第二步搜索的过程可以在O(n)的复杂度内完成。方法是，标记排序过后sortnumbers这串数的头和尾元素。通过比较sortnumbers[head]+sortnumbers[rear]与target之间的大小关系，对head和rear标记进行移动。

另外，看到通过使用HashTable实现的O(n)的算法，这个想法感觉和散列排序的想法差不多，没有过多的去关注。

---

代码

学习了下C++11的vector操作，用起来还真是不错。

调用algorithm库里的sort函数，以后再也不用裸写排序了 XD

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target)
    {
        vector<int> ans;
        vector<int> sortnumbers = numbers;
        sort(sortnumbers.begin(), sortnumbers.end());
        for (int i=0; i<sortnumbers.size(); ++i)
        {
            int sol = 0;
            sol = check(sortnumbers, target-sortnumbers[i], 0, sortnumbers.size()-1);
            if (sol != -1)
            {
                for (int j=0; j<numbers.size(); ++j)
                {
                    if (sortnumbers[i] == numbers[j])
                    {
                        ans.push_back(j+1);
                        break;
                    }
                }
                for (int j=numbers.size()-1; j>=0; --j)
                {
                    if (sortnumbers[sol] == numbers[j])
                    {
                        ans.push_back(j+1);
                        break;
                    }
                }
                break;
            }
        }
        if (ans[0] > ans[1]) {
            vector <int> rans;
            rans.push_back(ans[1]);
            rans.push_back(ans[0]);
            return rans;
        }
        return ans;
    }
    int check(vector<int> &sortnumbers, int n, int low, int high)
    {
        if (low == high)
        {
            if (sortnumbers[low] == n) return low;
            else return -1;
        }
        else if (low < high)
        {
            int mid = (low+high)/2;
            if (sortnumbers[mid] < n) check(sortnumbers, n, mid+1, high);
            else check(sortnumbers, n, low, mid);
        }
    }
};

转载于:https://my.oschina.net/yamamaki/blog/224383