LeetCode : 1. Two Sum

 

 

 

문제)

nums 벡터안에 있는 정수 중 2개를 더해서 target 값을 구할 수 있는 정수의 인덱스를 가진 벡터를 리턴 해주면 되는 문제.

난이도 : 하

 

소요시간 및 풀이)

딱 보기에도 쉬운 문제라고 생각되어서 내가 생각해본대로 풀었는데 다행히 정답이었다.

 

단순하게 이중 for문으로 접근해서 두 인덱스를 더해서 그 결과가 target인지 확인했다.

거품 정렬과 비슷한 느낌.

20분정도 소요 한듯.

 

정답을 맞추고 다른 사람들 코드를 보니 코드의 성능을 위해 해시 맵을 많이 사용했다.

나도 다음에 이런류의 문제가 나온다면 해시 맵을 사용하면 될 것 같다.

 

정답 코드

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

        for (int i = 0; i<nums.size(); i++)
        {
            for (int j = 1; j < nums.size(); j++)
            {               
                if (i == j)
                    continue;
                    
                auto val = nums[i] + nums[j];
                
                if (val == target)
                {
                    vec.push_back(i);
                    vec.push_back(j);
                    return vec;
                }
            }
        }

        return vec;
    }
};

 

 

해시 맵을 사용한 성능이 더 좋은 코드

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap;
        int n = nums.size();

        // Build the hash table
        for (int i = 0; i < n; i++) {
            numMap[nums[i]] = i;
        }

        // Find the complement
        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.count(complement) && numMap[complement] != i) {
                return {i, numMap[complement]};
            }
        }

        return {}; // No solution found
    }
};