3주차. 배열(두수의 합)

 

07. 두수의 합

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

Two Sum - LeetCode

 

 

📌문제
덧셈하여 타겟을 만들 수 있는 배열의 두 인덱스를 리턴하라

  
- 예제1
  📝입력

 nums = [2,7,11,15], target = 9

  💻출력

[0,1]

  
 - 예제2

  📝입력
 

 nums = [3,2,4], target = 6

  💻출력
 

[1,2]

    
📌풀이
1. 브루트포스(113ms, 42.8mb)

public int[] twoSum2(int[] nums, int target) {
        // 배열 인덱스를 돌면서 target을 찾음
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                // 같은 인덱스끼리의 합이면 continue
                if (i == j) continue;
                if (nums[i] + nums[j] == target) return new int[]{i ,j};
            }
        }
        return new int[]{};
    }

 

2. Map 활용(1ms, 42.3mb) 

public int[] twoSum(int[] nums, int target) {
    // list의 contain 시간복잡도 O(N) 사용X, set은 검색이 불가하다, map 밖에 없겠군
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        // containkey함수가 시간복잡도 0(1), value는 O(N)
        // containkey함수를 사용하기 위해서 배열 값을 key값으로 잡음
        if(map.containsKey(target - nums[i])) return new int[]{i ,map.get(target - nums[i])};
        map.put(nums[i], i);
    }
    return new int[]{};
}

- 이중반복문을 피하기 위해 map을 활용했다.

- 주석처럼 containKey함수를 활용하면 시간 복잡도를 대폭 줄일 수 있다.