LeetCode #1 两数之和

哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,size_t> t;
        int i = 0;
        while(1){
            t.insert(pair<int,size_t>(nums[i],i));
            if(t.find(target-nums[i])!=t.end() && t[target-nums[i]]!=i){
                vector<int> answer;
                answer.push_back(t[target-nums[i]]);
                answer.push_back(i);
                return answer;
            }
            i++;
        }
    }
};

排序

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> sortnums;
        sortnums = nums;
        sort(sortnums.begin(),sortnums.end());
        vector<int> t;
        t.push_back(0);
        t.push_back(nums.size()-1);
        while(1){
            if(sortnums[t[0]]+sortnums[t[1]]==target){
                break;
            }
            else if(sortnums[t[0]]+sortnums[t[1]]>target){
                t[1]--;
            }
            else{
                t[0]++;
            }
        }
        vector<int> answer;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==sortnums[t[0]]){
                answer.push_back(i);
                continue;
            }
            if(nums[i]==sortnums[t[1]]){
                answer.push_back(i);
            }
        }
        return answer;
    }
};