[leetcode - Java] 1. Two Sum

1. 문제

---

- 배열의 요소를 더해 target이 되는 값을 찾고 해당 값들의 인덱스번호를 반환

2. 의사 코드

---

배열의 모든 값을 검사하는 완전 탐색을 제외하고 두 가지를 생각했던 것 같다. 요소들을 더해 target을 찾을 것인지, target에서 요소들을 빼면서 찾아갈 것인지. 아래는 target에서 요소들을 빼가는 코드이다.

1. target에서 배열의 요소들 - 하기
    for(int i=0; 배열 길이만큼; i++) {
        int minus = target - 배열 요소;
        if 배열 요소가 map에 있다면
            return [인덱스, map에서 찾은 값];

        map.put(키, 벨류)
    }

3. 시도

---

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] arr = new int[2];

        for(int i=0; i<nums.length; i++) {
            int minus = target - nums[i];
            if(map.containsKey(minus)) {
                arr[0] = map.get(minus);
                arr[1] = i;
                return arr;
            }
            map.put(nums[i], i);
        }

        return arr;
    }
}

원래는 키값을 i(인덱스번호)로 하려고 했지만 키값을 i로 했다면 containsKey가 containsValue로 바뀌고, arr[0] = map.get(minus);를 할 때 map.get 함수로 벨류를 불러올 수 없었기에 i를 벨류값으로 넣었다.

---

추가로 완전 탐색 코드는 아래와 같다.

class Solution {
    public int[] twoSum(int[] nums, int target) {

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

배열의 모든 요소를 탐색하기 위해 반복문을 두 개 사용한다. 시간 복잡도는 O(n^2)가 예상되며 map을 사용한 시간 복잡도는 배열 한 번을 돌아야 하기에 O(n)이 예상된다. 문제를 풀어갈수록 같은 기능을 구현하는데도 생각할 것이 참 많은 것 같다.