lintcode之两数之和

题目：

给一个整数数组，找到两个数使得他们的和等于一个给定的数target。

你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是1到n，不是以0开头。

解答：

hash + 排序 + two pointers,注意数是可能重复的

class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     */
    vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here
        map<int, vector<int>> record;
        for (int i = 0;i < nums.size();++i) {
            record[nums[i]].push_back(i);
        }
        sort(nums.begin(), nums.end());
        int start = 0;
        int end = nums.size() - 1;
        while (start < end) {
            if (nums[start] + nums[end] == target) {
                if (nums[start] == nums[end]) {
                    return {record[nums[start]][0] + 1, record[nums[start]][1] + 1};
                } else {
                    if (record[nums[start]][0] < record[nums[end]][0]) {
                        return {record[nums[start]][0] + 1, record[nums[end]][0] + 1};
                    } else {
                        return {record[nums[end]][0] + 1, record[nums[start]][0] + 1}; 
                    }
                }
            }
                 else if (nums[start] + nums[end] > target) {
                    end--;
                } else {
                    start++;
                }
            }
    }
};

阅读更多