leet code (1) - two sum

알고리즘 풀이 1일차

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

문제설명

정수를 담은 배열 nums 와 정수 target 이 주어진다.
합이 target 이 되는 두 수를 배열에서 찾고, 그 인덱스를 반환하라.

풀이

처음 시도한 방법

    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];

        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 result;
    }

반복문을 돌면서 두 개의 수를 이룰수 있는 모든 짝을 찾아보았다.
배열을 이중으로 순회하기 때문에 N^2 의 복잡도를 가진다.

 

 

그리고 솔루션에 나오는 다른사람의 풀이를 보고 다시 풀어보았다.

    public int[] twoSumByHashTable(int[] nums, int target) {
        Map<Integer, Integer> numAndIndex = new HashMap<>();

        for (int index = 0; index < nums.length; index++) {
            int pair = target - nums[index];

            if (numAndIndex.containsKey(pair)) {
                int pairIndex = numAndIndex.get(pair);

                return new int[] {pairIndex, index};
            }
            numAndIndex.put(nums[index], index);
        }
        return new int[] {};
    }

이 풀이법의 아이디어는 배열을 순회하면서 해쉬맵에 [값, 인덱스] 를 저장하고
현재 인덱스의 값과 합쳤을때 target 이 되는 짝 값이 해쉬맵에 있는지 비교하는 것이다.

 

해쉬맵에 배열만큼 저장해야하기에 메모리 공간을 더 차지하겠지만(최대 N만큼)
배열을 1번만 순회하기때문에 시간복잡도가 N 으로 줄어든다.