Two Sum

题目1: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

题目意思是从给定一组数中,选出2个数,他们的和满足给定的一个目标值,按顺序输出这两个数对应的索引。(假设正好只有一个解)
思路:先按从小到大顺序数组排序,然后从小到大依次遍历,先确定一个较小的数,然后再其后面的数中使用二分查找的方式找另外一个数。

class Solution {
public:
    struct Item{
        int value;
        int index;
        Item(int pvalue, int pindex):value(pvalue), index(pindex){};
        bool operator<(const Item &it)
        {
            return value < it.value;
        }
    };
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        vector<Item> data;
        for(int i = 0; i <nums.size(); i++)
        {
            data.push_back(Item(nums[i], i));
        }
        sort(data.begin(), data.end());
        int lindex = 0, rindex = data.size() - 1;
        for( int lindex = 0; lindex <= rindex; lindex++){
            if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target)){
                result.push_back(min(data[lindex].index+1, data[lindex+1].index+1));
                result.push_back(max(data[lindex].index+1, data[lindex+1].index+1));
                return result;
            }
            else if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target))
                continue;
            int ret = -1;
            int remain = target - data[lindex].value;
            int left = lindex, right = rindex;
            while(left <= right){
                int mid = (left+right)/2;
                if(data[mid].value == remain){   // must compare the index
                    result.push_back(min(data[lindex].index+1, data[mid].index+1));
                    result.push_back(max(data[lindex].index+1, data[mid].index+1));
                    return result;
                }
                else if(data[mid].value < remain){
                    left = mid + 1;
                }
                else
                    right = mid - 1;
            }
        }
    }
};

时间复杂度为O(nlogn)
听说使用hashmap能将为O(n) 后续再探讨

Leave a Reply

Your email address will not be published. Required fields are marked *