1. Two Sum

 

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

불러오는 중입니다...

 

두 수를 더해서 target의 값과 같으면 두 수의 index를 반환하는 문제

 

Bruth-force 접근

모든 경우의 수를 모두 탐색 하면 되니까 모두 찾아본다 2중 반복문이라서 일단 O(n)^2

Runtime: 224 ms, faster than 13.61% of C++ online submissions for Two Sum.

Memory Usage: 9.2 MB, less than 94.82% of C++ online submissions for Two Sum.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> arr;
        const int size = nums.size();
        
        for(int i=0; i<size; i++) {
            int left = nums[i];
            bool find = false;
            for(int j=0; j<size; j++) {
                
                if(i==j) {
                    continue;
                }
                
                int right = nums[j];
                if(left + right == target) {
                    arr.push_back(i);
                    arr.push_back(j);
                    find = true;
                    break;
                }
            }
            
            if(find) {
                break;
            }
        }
        
        return arr;
    }
};

 

INDEX 사용 하는 방법으로 접근

배열의 모든 요소의 값을 map에 키 값으로 설정, map 값은 index로 설정

두 수의 합을 찾는 문제이니까 target의 값에서 임의의 요소를 뻴셈하여 뺄셈 한 결과가 map에 있는지 확인하는 방법으로 풀이

음 시간복잡도는 배열의 크기 만큼 반복 하니까 O(n) + O(n) = O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> arr;

        unordered_map<int, int> m;
        const int size = nums.size();

        // vector 의 값을 키, 배열의 인덱스를 값으로
        for (int i = 0; i < size; i++) {
            m[nums[i]] = i;
        }

        for (int i = 0; i < size; i++) {

            int cand = target - nums[i];

            if (m.count(cand)) {
                int d = m[cand];
                if (i == d) {
                    // 같은 index 는 올수 없음
                    continue;
                }
                arr.push_back(min(i, d));
                arr.push_back(max(i, d));
                break;
            }
        }

        return arr;
    }
};