문제

https://leetcode.com/problems/two-sum/
정수 배열과 target이 주어졌을 때, 배열에서 선택한 두 값의 합이 target값과 같아지도록 하는 값의 인덱스를 구한다.

O($n^2$), 85ms

문제를 처음 보았을 때 직관적으로 이중 for문을 활용하여 풀어야겠다고 생각했다.

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[] {0, 0};
    }
}

그 결과 시간 복잡도가 상위 77%가 나왔다.

O($n$), 2ms

자료구조를 잘 활용하면 시간복잡도 개선할 수 있다.
정수 값을 key로 갖고, 배열의 인덱스를 value로 가지는 map을 이용하여 문제를 해결하였다.

import java.util.HashMap;
import java.util.Map;

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

			return new int[] {};
		}
	}