[LeetCode] Two Sum

Link

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

---

Code

// Naive Code
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 new int[] {};
    }
}

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

---

Solution

해시맵을 만들고 nums를 순회하면서 temp(target - nums[i])를 계산해 현재 해시맵에 존재하는지 체크를 하고 존재하면 바로 [i, map.get(temp)]를 리턴하고 아니면 map에 (nums[i], i)를 삽입한다. for문이 다 돌때까지 리턴하지않으면 빈 배열을 리턴, 이렇게 되면 시간복잡도가 O(n)으로 해결 가능
너무 오랜만에 풀어 배열 리턴 방법도 몰라서 검색해서 알게되었다. 그리고 다른 분들의 코드를 보니 쉬운 문제라고 너무 나이브하게 푼것같아 부끄러웠다. 자주 연습해야겠다.