1. Two Sum

문제설명

정수형 배열 nums와 정수 target이 주어졌을 때, 두 수의 합이 target이 되는 인덱스들을 출력하시오. 각 입력의 솔루션은 오직 하나이고, 같은 원소를 중복해서 사용할 수 없고, 출력되는 인덱스의 순서는 상관없다.

출력예시

접근 방법

첫번째 시도

시간복잡도 O(n^2)보다 작은, 완전 탐색을 제외한 해결 방법을 찾아보자...
해시테이블을 이용해보자. 인덱스와 값을 반대로 넣은 배열을 생성해본다
ex) nums=[2,7,11,5] -> arr[2]=0, arr[7]=1, arr[11]=2, arr[5]=3
하다가 음수인 경우는 생각 못 함... fail

두번째 시도

unordered map을 사용하기 !! (key - value) ={value,index}로 구성한다.
이때 하나의 원소를 삽입할때, 짝이 되는 원소(target_B)가 있는 지 살펴보고 있다면 그 두 인덱스 값이 정답이 되어 종료하도록 한다.
짝이 되는 원소가 없다면 insert.

소스코드

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m; 
        bool flag=true;
        vector<int> answer;
        for(int j=0; j<nums.size(); j++){
            int target_B = target - nums[j];
            if(m.find(target_B)!=m.end()){
                answer.push_back(j);
                answer.push_back(m[target_B]);
                break;
            }
            else {
                m.insert({nums[j],j});
            }
        }
        return answer;
    }
};

돌아보기

unordered_map을 이용하면 insert,find,erase가 O(1)의 속도로 진행된다.
해시를 떠올릴 때, 단순 1차원 배열이외에도 맵 떠올리기...
또 문제 풀 때 일단 맵 안에 모두 insert하고 고민하는 느낌이였는데, 중복 여부를 확인하는 방법을 한 번의 반복문 안에서 해결하는 방법을 잘 익혀둬야겠다.
map/set/unordered_map/unordered_set 공부를 더 해야겠다.