Today I Learned

오늘도 안드 공부 하면서 leetcode에서 코딩테스트를 쭉 풀었다.
여러 문제 중 한 문제만 여기서 정리를 해보려 한다.

1. Two Sum

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

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Can you come up with an algorithm that is less than O(n2) time complexity?

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

풀이과정

• 두 값을 찾아야 되는데 O(n^2)의 이중 for문은 통과하지 못한다. 그래서 첫 시도는 투포인터로 시도했다. 투포인터를 이용하면 정렬만 한다면 O(n)으로도 간단하게 찾을 수 있을꺼라 생각했다. 하지만 정렬이 문제였다.

• 정렬전과 정렬후 index 자체가 달라지기 때문에 정렬 전 index 기록 -> 정렬 -> 투포인터 -> 답안 토대로 정렬전 index 찾기의 과정이 너무 번거로워졌다.

• 그래서 map을 활용해서 푸는 방법으로 변경했다.
  배열을 순회하는 for문을 만들어 배열 안의 값과 타겟간의 차이(complement)를 구해 이 값이 map에 있는지 확인하고 있으면 두 값의 인덱스를 반환한다.

• 만약 없으면 순회하고 있는 값의 index를 value에, 값을 key로 해서 map에다 삽입한다.

Java 코드

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