1. Two Sum

문제 링크: https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150

문제

nums 배열에서 합이 target이 되는 두 요소의 index를 찾자.

• 각 입력에는 하나의 솔루션이 있다고 가정

입력

• 정수 배열 nums
• 정수 target

출력

• 정수 배열 (정렬 상관 X)

---

나의 풀이

접근

일단 target이 되는 여러 요소가 아닌 두 요소만 찾아도 된다는 점이 포인트라고 생각했다.

그렇다면 nums에 있는 각 값들을 O(1)의 시간복잡도로, 바로바로 찾을 수 있게 하고, 다른 하나의 요소는 nums를 천천히 탐색하며 찾으면, O(n)의 코드를 작성할 수 있지 않을까?

→ Hash Table 을 사용하자

구현 코드

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

• (값, 인덱스) 이런 형태로 nums의 요소를 저장할 HashMap을 선언
• for문을 실행하며, nums의 요소 탐색
• 만약 map에 target-nums[i]의 키를 가진 데이터가 있다면,
  • 키가 target-nums[i]인 value와, 현재 탐색하고 있던 요소의 index 배열을 return
• 아니라면, map에 (키=nums[i], 값=i) 를 삽입

결과

Time: O(n)

Space: O(n)

---

다른 풀이

Java를 이용한 다른 풀이는 더 성능이 좋지 않거나, 나와 비슷한 코드이므로 따로 기록하지 않겠다.