리트코드 투썸 c++ // pair 이분탐색 방법 , 해쉬맵, nC2 O(n) 구현방법

https://leetcode.com/problems/two-sum/

 

1. pair 이분탐색 방법

1.1 lower_bound(begin, end, pair<int,int>{a,b}) 이렇게 넣어줘야함

 

1.2. 시행착오

diff = target - num 이렇게 둬야함 // abs씌울필요 없음! 

ex) 2에서 target이 0이면, -2를 찾으면 됨

 

1.3. 시간복잡도 : 정렬(nlgn) + 각원소에대해 이분탐색(nlgn)

 

typedef pair<int, int> pii;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int, int>> v; // {value, index}
        for (int i = 0; i < nums.size(); ++i) {
            v.push_back({nums[i], i});
        }
        sort(v.begin(), v.end());
        
        for (int i = 0; i < v.size(); ++i) {
            int complement = target - v[i].first;
            auto it = lower_bound(v.begin() + i + 1, v.end(), pii(complement, 0));
            if (it != v.end() && it->first == complement) {
                return {v[i].second, it->second};
            }
        }
        return {}; // Return an empty vector if no pair is found
    }
};

 

2. 해쉬맵

2.1. 의사코드

map<값, idx>을 만들고

이미 존재하면, 그걸 리턴해주면 됨. 

존재여부는 map.count함수를 이용하면 된다!

주의 : map을 지역변수로 해줘야, tc마다 자동초기화가 된다.

 

2.2. 시간복잡도 : O(n)

2.3. 전체코드

class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numMap; //매 tc마다 자동초기화 되도록
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (numMap.count(complement)) { //map.count함수 => 키값존재 검사!
            return {numMap[complement], i};
        }
        numMap[nums[i]] = i;
    }
    return {};
  }
};