LeetCode - Two Sum

Two Sum - LeetCode

 

나의 풀이

 

import java.util.*;

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

 

떠올린 방식

 

1. brute force

    - time complexity : O(n^2)

    - logic : 이중 for 문

    - 더 효율적인 로직을 떠올려보자..

 

2. sort

    - time complexity : O(nlogn)

    - logic : 정렬 이후 왼쪽 끝, 오른쪽 끝에서 각각 시작해 범위 줄여나가기

    - 기존의 인덱스 정보를 가지려면 배열을 복사해야하며, 정렬 이후 찾은 세트의 인덱스를 찾는 과정에서 소모값이 크다고 판단

 

3. hashmap

    - time complexity : O(n)

    - logic : 배열을 돌면서 해당 숫자와 인덱스를 각각 key, value에 넣어두고 이후 숫자에서는 자신의 짝이 이미 존재하는지 containKey를 이용해 찾기

    - containKey는 상수 시간이므로 가능한 로직

 

 

결과

 

 

---

다른 사람의 풀이

 

나의 최종 풀이와 같았다.