[LeetCode - 1] Two Sum - Java

문제 설명

 

Two Sum - LeetCode

 

 

풀이 : Success

소스 코드

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

        int len = nums.length;

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

        return null;
    }
}​

 

풀이 회고

배열에 있는 원소들의 합의 모든 경우를 검색하기 위해 2중 for문을 사용하여 nums 배열을 탐색하도록 했고 찾고자 하는 값(target)이 있을 경우 해당하는 인덱스 번호들을 return 하도록 했다. 하지만 이러한 방법은 직관적이지만 상대적으로 시간복잡도 성능이 좋지 않다.

 

모범 소스코드

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

 

코드 분석

해당 풀이에서는 HashMap 자료구조를 사용했는데, 우선 단일 for문으로 nums 배열을 탐색하면서 목표하는 값(target)에서 탐색된 원소만큼의 수를 뺀 값을 key로, 해당 원소의 인덱스를 value로 HashMap에 put 해주었다.

 

또한 if문을 통해 탐색된 원소가 해당 HashMap에 키 값으로 존재하는지 체크하는데, 만약에 존재한다면 이는 nums[i]라는 값과 target - nums[i 보다 작은 인덱스]가 일치한다는 것으로, nums[i 보다 작은 인덱스]와 nums[i]를 합하면 target과 같다는 것을 의미한다.

 

이렇게 푼다면 앞서 2중 for문으로 모든 경우의 합을 탐색할 때보다 훨씬 성능이 개선될 것이다.

 

 

참고자료

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