기억하고싶은것들

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.

정수 배열 nums와 정수 target이 주어진다.

배열의 두 수를 더해서 target이 되는 숫자를 반환하라.

주어진 배열에 정답이 되는 쌍은 정확히 하나이고, 같은 숫자들을 중복해서 사용할 수 없다.

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), O(nlogn), O(n^2)

각각의 방식들에 맞는 솔루션이 어떤 것이 있는지 고민하며, 가장 최적화된 방법으로 문제를 풀어나가 보자.

우선 가장 단순하게 배열을 2중으로 순회하며 값을 비교할 수 있다.

O(n^2)

    public int[] twoSum(int[] nums, int target) {

        for (int i = 0; i < nums.length - 1; i++) {
            int num1 = nums[i];
            for (int j = i + 1; j < nums.length; j++) {

                if (target - num1 == nums[j]) {
                    return new int[] { i, j };
                }
            }
        }

        return null;
    }

또한, HashMap을 이용해서 배열은 한 번만 순회하는 방법도 존재한다. 

O(n)

    // time complexity - o(n)
    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap<>();
        int t = 0;
        for (int i = 0; i < nums.length; i++) {
            t = target - nums[i];
            if (map.containsKey(t)) {
                return new int[] { i, map.get(t) };
            } else {
                map.put(nums[i], i);
            }
        }
        return null;
    }