(C++) - LeetCode (easy) 1. Two Sum

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

Two Sum - LeetCode

여러 풀이 방법이 가능한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

여러 수들이 담긴 nums와 두 수의 합이 target값이 되어야 합니다.

📔 풀이과정

📑 Brute force O(n^2)

이중 for loop로 해결 가능합니다.

nums의 원소들을 순회하며 순서 상관없도록 2개의 수를 뽑는다고 생각하면 됩니다. nums[i] + nums[j] = target이라면 정답 {i, j}를 반환합니다.

 

📑 Binary Search O(nlog(n))

1. 정렬되기 전 vector originNums를 선언해 nums를 저장해줍니다.num

 

2. 정렬되기 전 map인 m을 선언 후 nums를 순회하며 key에는 nums원소값, value에는 nums의 index를 m에 저장해줍니다.

 

3. nums를 오름차순으로 정렬해줍니다. 이분탐색에는 정렬된 원소에 대해 시행해야 하기 때문입니다.

 

4. nums의 원소를 순회합니다. i번째 원소는 고정이므로 나머지 한 개의 수만 이분탐색으로 찾으면 됩니다. 순회하며 target - nums[i]인 lower_bound를 찾아줍니다. 두 수를 더했을 때 target과 같다면 정답을 찾았으므로 정답 vector ans에 해당 값의 원래 index를 m으로부터 찾아 저장합니다.

 

5. map에 index를 저장했으므로 target이 6, ans = {3,3}인 경우 같은 index를 정답으로 반환하는 경우를 방지하기 위해 originNums를 사용합니다. ans[0] == ans[1]인 경우 originNums를 순회하며 찾은 값에 해당하는 index들을 뽑아 ans2에 저장 후 바로 반환합니다.

 

📑 HashMap이용 O(nlog(n))

1. hashmap m을 선언합니다.

2. nums의 원소들을 순회합니다. 매 순회마다 다음을 수행합니다.

  2-1. target - nums[i]에 해당하는 index가 m의 value로 존재하는지 확인합니다. 존재한다면 break해줍니다.

  2-2. m의 key로는 nums의 i번째 원소, value로는 i를 저장해줍니다.

---

📕 Code

📔 C++

📑 Brute force O(n^2)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector <int> ans;
        for(int i = 0; i < nums.size(); i++){
            for(int j = i+1; j < nums.size(); j++){
                if(nums[i] + nums[j] == target) {
                    ans = {i,j};
                    break;
                }
            }
        }
        return ans;
    }
};

 

📑 Binary Search O(nlog(n))

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector <int> ans;
        vector <int> originNums = nums;
        map <int,int> m;

        for(int i = 0; i < nums.size(); i++) {
            m[nums[i]] = i;
        }
        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size(); i++){
            auto it = lower_bound(nums.begin() + i + 1, nums.end(), target-nums[i]);
            if(it == nums.end()) continue;
            int idx = it - nums.begin();
            if(nums[i] + nums[idx] == target) {
                ans = {m[nums[i]], m[nums[idx]]};
                break;
            }
        }

        if(ans[0] == ans[1]) {
            vector <int> ans2;
            for(int i = 0; i < originNums.size(); i++) {
                if(originNums[ans[0]] == originNums[i]) ans2.push_back(i);
            }
            return ans2;
        }

        return ans;
    }
};

 

📑 HashMap이용 O(nlog(n))

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> m;
        vector <int> ans;
        for(int i = 0; i < nums.size(); i++) {
            int other = target - nums[i];
            if(m.count(other)) {
                ans = {i, m[other]};
                break;
            }
            m[nums[i]] = i;
        }
        return ans;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.