[leetcode]Two Sum II - Input array is sorted

유의할점

해쉬 테이블

풀이

투포인터 : O(N)

해쉬테이블 : O(N)

코드

C++ : 투포인터

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0;
        int r = numbers.size()-1;
        int sum;
        while((sum=numbers[l]+numbers[r])!=target){
            if(sum < target){
                l++;
            }else{
                r--;
            }
        }
        vector<int> res;
        res.push_back(l+1);
        res.push_back(r+1);
        return res;
    }
};

C++ : 해쉬 테이블

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int,int> umap;
        for(int i = 0; i < numbers.size(); i++){
            int dif = target - numbers[i];
            if(umap[numbers[i]]){
                return vector<int>({umap[numbers[i]],i+1});
            }
            umap[dif] = i+1;
        }
        return vector<int>();
    }
};