Two Sums

🔗 문제 링크

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

🔍 문제 설명

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.

⚠️ 제한사항

• $2 <= nums.length <= 10^4$

• $-10^9 <= nums[i] <= 10^9$

• $-10^9 <= target <= 10^9$

• Only one valid answer exists.

---

🗝 풀이 (언어 : Java)

이중 반복문으로 풀게되면 $O(N^2)$의 시간복잡도가 되므로, 반복문을 한번 돌면서 푸는 방법을 생각해야 한다. 인덱스를 해당 값과 같이 보관하기 위해 HashMap을 사용했다. 그리고 짝을 찾는 과정을 반복문을 한번 돌때 같이 체킹하기 위해서 (해당 수의 짝이 되는 값 = target - 해당 수)를 이용했다.

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        // 해당 값과 인덱스를 같이 보관할 map
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // nums[i]의 값과 짝을 이룰수 있는 값
            int pair = target - nums[i];
            // 이미 전순서에 넣어져있다면 정답 반환
            if (map.containsKey(pair)) {
                answer[0] = i;
                answer[1] = map.get(pair);
                break;
            }
            // 아직 해당 수의 짝의 값이 map에 없으면 해당 수 넣고 조회 재개
            else
                map.put(nums[i], i);
        }
        return answer;
    }
}