[LeetCode] 1번 - Two Sum [Java][C++]

문제 링크

---

1. 아이디어

정수 배열 nums와 정수 target이 주어졌을 때, nums에서 두 수의 합이 target이 되는 쌍이 딱 하나 존재하며 이때 두 수의 인덱스를 찾는 문제다.

간단한 방법으로는 2중 반복문을 통한 브루트 포스로 해결할 수 있다. 바깥쪽 반복문이 두 수 중 앞쪽 인덱스를, 안쪽 반복문이 뒤쪽 인덱스를 찾아내는 방식으로 구현해줬다.

다음으로 $O(N^2)$ 보다 빠른 복잡도로도 해결할 수 있는데 이를 위해 해시맵을 활용해줬다. 기본 아이디어는 nums의 원소에 대해 원소의 값을 key, 원소의 인덱스를 value로 갖는 해시맵을 만든 후 nums의 각 원소에 대해 target에서 해당 원소를 뺀 값이 해시맵에 key로 존재하면 두 수를 찾은 것이 된다. 다만 이때 nums에는 동일한 수들이 등장할 수 있다는 점과 같은 원소를 두 번 선택하면 안된다는 제약이 존재한다. 먼저 동일한 수들이 등장할 수 있는 경우를 보면 특정 수가 1번 등장한 경우는 아무 문제 없으며, 2번 등장한 경우는 해당 두 수가 target을 만드는 두 수가 되는 경우가 아니면 두 수는 모두 target을 만드는 후보가 될 수 없다. 특정 수가 3번 이상 등장한 경우는 해당 수는 target의 후보가 될 수 없다.

---

2. 복잡도

1. 브루트 포스

시간복잡도	공간복잡도
$O(N^2)$	$O(1)$

2. 해시맵

시간복잡도	공간복잡도
$O(N)$	$O(N)$

---

3. 코드

1. 브루트 포스 [Java][C++]

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[]{i, j};
            }
        }

        return null;
    }
}

#include <bits/stdc++.h>
using namespace std;

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

        return {};
    }
};

2. 해시맵 [Java][C++]

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && nums[i] * 2 == target) {
                return new int[]{map.get(nums[i]), i};
            }
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i]) && nums[i] * 2 != target) {
                return new int[]{i, map.get(target - nums[i])};
            }
        }

        return null;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); i++) {
            auto it = mp.find(nums[i]);
            if (it != mp.end() && nums[i] * 2 == target) {
                return {it->second, i};
            }
            mp[nums[i]] = i;
        }

        for (int i = 0; i < nums.size(); i++) {
            auto it = mp.find(target - nums[i]);
            if (it != mp.end() && nums[i] * 2 != target) {
                return {i, it->second};
            }
        }

        return {};
    }
};

---