1. Two Sum

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

Two Sum - LeetCode

난이도 : easy

문제

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라

 

정수형 원소로 두개의 합의 target 과 같다면 해당 원소의 index 반환 하여 풀이 하면 된다.

1. map 을 선언하고 key 를 배열의 값 value 를 인덱스로 삽입한다.

2. 반복문을 순회하면서 target 을 배열의 값으로 뺄셈 연산을 한다. 뺄셈 연산한 결과값이 map 있으면 각각의 inddex 를 리턴 한다.

이문제는 만약 값을 찾아내는 문제라면 배열을 정렬하고 two pointer 로 접근하는 생각이 가능해 보일수 도 있지만 index 를 찾아내는 문제이기 때문에 two pointer 를 사용하면 안된다. 만약 문제의 조건중에 정렬된 상태로 온다면 two pointer 로도 가능하다.

코드

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;
    }
};

 

상기 코드를 깔끔하게 짠다면 아래와 같다.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> indices;
        for (int i = 0; i < nums.size(); i++) {
            
            // target 에서의 차이가 map 에 없으면 map 에 값과 index 를 저장한다
            if (indices.find(target - nums[i]) != indices.end()) {
                return {indices[target - nums[i]], i};
            }
            indices[nums[i]] = i;
        }
        return {};
    }
};