LeetCode 1. Two Sum

題目連結： Two Sum – LeetCode

前言

最近想說來寫一下許多人推薦的 LeetCode。

想法

我是用 pair 額外儲存陣列中元素的 index ，並用排序加上二分搜的方法。因為這題的 n 最多是 10000，我不確定 O(n^2) 的演算法會不會過，所以就決定用 O(nlog(n))，…一個比較保險的概念。

code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int,int>> v(nums.size());
        for(int i=0;i<nums.size();++i){
            v[i].first=nums[i];
            v[i].second=i;
        }
        sort(v.begin(),v.end());

        vector<int> ret;
        for(int i=0;i<nums.size();++i){
            int a=v[i].first;
            int it=lower_bound(v.begin()+i+1,v.end(),make_pair(target-a,0))-v.begin();
            if(it>=nums.size()) continue;
            int b=v[it].first;
            if(a+b==target){
                ret.emplace_back(v[i].second);
                ret.emplace_back(v[it].second);
                return ret;
            }
        }
        return ret;
    }
};