[LeetCode] 1. Two Sum

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

Two Sum - LeetCode

설명

방법1. n^n 풀이 방법

이중 반복문을 이용했다. 

target에서 첫번째 선택한 값을 뺀 것을 remains라고 하고, 첫번째 인덱스 이후부터 반복을 통해 remains와 같은 값이 있는지 확인하고 만약 있다면 answer를 업데이트하고 break하였다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];

        for(int i = 0; i < nums.length; i++) {
            int remains = target - nums[i];
            for(int j = i+1; j < nums.length; j++) {
                if(nums[j] == remains) {
                    answer[0] = i;
                    answer[1] = j;
                    break;
                }
            }
        }

        return answer;
    }
}

 

방법2. n 풀이 방법

remains와 index를 함께 저장한다.

만약 탐색하다가 배열에서 remains가 검색되면, answer를 업데이트하고 리턴한다.

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

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

        return answer;
    }
}