PS

Leetcode 1. Two sum

Bryan Lee 2022. 5. 3. 12:30

문제 이해

- 배열에서 Target과 일치하는 두 수의 합을 구하라

 

해결 전략

(1) O(n2)으로 문제를 풀이하면,  2중 for문을 순회하면서 목표하는 target을 구할 수 있습니다. 

(2) O(n)으로 문제를 풀이하면, HashMap을 사용해서 목표하는 target을 구할 수 있습니다. 

 

구현

(1) O(n2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int[] answer = 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){
                    answer[0] = i;
                    answer[1] = j;
                }
            }
        }
        
        return answer;
    }
}

 

(2) O(n)

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(target-nums[i])){
                answer[1] = i;
                answer[0] = map.get(target-nums[i]);
                return answer;
            }
            
            map.put(nums[i], i);    
        }
        
        return answer;
        
    }
}

 

피드백

- HashMap을 사용해 O(n)으로 문제를 풀이하는 법을 아는 것이 중요합니다.

- HashMap의 내부 구조에 대해서도 잘 알아야 합니다. 

'PS' 카테고리의 다른 글

Leetcode 2. Add Two Numbers  (0) 2022.04.30
Leetcode 21. Merge Two Sorted Lists  (2) 2022.04.26
Leetcode 234. Palindrome Linked List  (1) 2022.04.26
Leetcode 203. Remove Linked List Elements  (1) 2022.04.26
Leetcode 876. Middle of the Linked List  (0) 2022.04.25