<leet code> Two sum

[https://leetcode.com/problems/two-sum/submissions/]

 

릿 코드 문제가 면접에 나오기 좋아 보인다.ㅎㅎ; 공부하자.

 

음 이 문제는 배열이 주어져 있을때, 특정 수가 되는 두 수의 위치를 구하는 것인데,

 

나는 어떻게 했냐면, 배열을 정렬하고, 합을 두 수로 만든다는 것에서, 작은 것과 큰것을 더하고 투포인터 방식으로 둘중에 한쪽을 줄여서 찾는 방식으로 풀었다.

 

이전에 백준에서 풀어본 문제라 그냥 자연스럽게 떠오른거 같다.....

 

근데 음 솔루션을 보니

 

1. 브루트 포스

2. 투패스 해쉬 테이블로 ,시간 절약 

왜 투패스냐면 두번 이터레이트 하는데, 첫번째는 해쉬테이블에 값을 넣고, 두번째는 타겟과의 차이값이 해쉬테이블에 있는지 확인 하는것이다.

 

3. 원패스 해쉬 테이블

그냥 한번의 이터레이션에서 한번에 넣고, 바로 값이 있는지 확인해도 된다.

 

**내가 사용한 방법은 투포인터다. 시간 복잡도는 o(logn)이긴 할듯.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int,int>>vec;
        for(int i=0;i<nums.size();i++){
            vec.push_back(make_pair(nums[i],i));
        }
        sort(vec.begin(),vec.end());
        
        int st = 0, dt = nums.size()-1;
        int sum ;
        
        while(st < dt){
            sum = vec[st].first + vec[dt].first;
            
            if( target <  sum ){
                dt --;
            }else if( target > sum){
                st++;
            }
            else{
                break;
            }
        }
        
        vector<int> ans;
        ans.push_back(vec[st].second);
        ans.push_back(vec[dt].second);
        return ans;
    }
};