[LeetCode] 1. Two Sum

Two Sum - LeetCode

int 배열이 주어지고 target이 주어지면 2개의 조합으로 target이 되는 조합을 반환하는 문제입니다.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

 

문제접근

투포인터를 사용해서 O(n)으로 해결할 수 있다고 판단하여 투포인터를 사용했습니다.

 

하지만 투포인터로는 정답을 받을수 없었습니다.

왜냐하면 배열의 요소들이 정렬되어있지 않기때문입니다.

만약 정렬을 한다면 index가 바뀌어값을 찾기 어렵습니다.

 

투포인터 - 실패

public int[] twoSum(int[] nums, int target) {
        Arrays.sort(nums);
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int cur = nums[l] + nums[r];
            if (cur == target) {
                return new int[]{l,r};
            } else if (cur > target) {
                r--;
            } else {
                l--;
            }
        }
        return new int[]{};
    }

 

   

다른방법이 떠오르지않아 브루트포스를 이용해서 문제를 풀었습니다.

    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[]{};
    }

 

시간복잡도

for문을 2번사용하고 있습니다.

O(n2)의 시간복잡도를 갖고있습니다.

 

다른사람의 풀이

해시테이블을 사용한 풀이입니다.

해시테이블에 nums[i] : 키, val : 값 저장합니다.

target - nums[i]가 해시테이블에 있다면 정답을 찾은것입니다.

 

주의할점은 자기 자신을 더하면 안됩다는 것입니다.

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

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],i);
        }

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

        return new int[]{};
    }

 

시간복잡도

Map의 조회, 삽입의 시간복잡도는 O(1)입니다.

따라서 nums배열을 1번 loop하는 로직이 최대이니

O(n)의 시간복잡도가 필요합니다.

 

느낀점

Map은 시간을 단축하기 정말 좋은 자료구조입니다.

메모리를 소비하는 단점이 있지만, 잘 활용한다면 효율적인 코드를 작성할 수 있을것 같습니다.

 

참고

LeetCode - The World's Leading Online Programming Learning Platform