[LeetCode/Java] 1. Two Sum

0. 문제

https://leetcode.com/problems/two-sum/description/?envType=study-plan-v2&envId=top-interview-150

1. 문제 설명

• 정수 문자열 nums가 주어질 때 정수 target을 만족하는 두 원소의 인덱스 값을 반환하시오.

2. 문제 풀이

2.1. 접근법(1) : 브루트 포스

• 가장 먼저 든 방법이다.
• 두 원소의 조합을 찾는 문제이므로 최대 O(n^2)의 시간 복잡도이고, nums의 길이가 최대 1만이니 최악의 경우 1억 번의 조회니 할 만하다고 생각했다.
• 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[]{i, j};
            }
        }
        return new int[]{};
    }
}

• 결과

2.2. 접근법(2) : 해시맵

• HashMap의 Key 값에 nums의 원소, Value에 인덱스 번호를 저장한다.
• nums를 조회하면서 target - nums[i] 값(tmp)을 구한다.
• tmp 값을 Key로 가지면서 해당 Key 값의 Value가 tmp가 아니면 nums[i]와 Value 값이 답이된다.
• 이 방법은 HashMap에 값을 넣는 시간 복잡도 O(n) + nums를 조회하면서 값을 찾는 시간 복잡도 O(n)이 걸리므로 O(n)의 시간 복잡도로 해결할 수 있다.
• 코드

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

• 결과

3. 개선점

3.1. 시간 복잡도 개선

• 해시맵을 사용한 풀이의 문제점은 맵에 값을 넣는 반복문 때문에 시간 복잡도가 늘어난다는 것이다.
• 처음부터 값을 넣지 않고 nums를 조회하면서 target - nums[i]를 Key로 갖는 값이 있으면 해당 값이 정답이 되고 없는 경우에 맵에 넣는 방식으로 구현하면 시간 복잡도를 줄일 수 있다. (참고)

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

• 결과