[LeetCode] 001. Two Sum JAVA

Two Sum - LeetCode

---

📌 문제

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.

---

📌 방법 1. 반복문을 이용한 풀이

• 배열의 길이만큼 반복문을 이용
• 더한 두 수가 target과 일치하는지 확인
• 만들 수 없으면 빈 배열을 리턴
• 이중 반복문으로 시간 복잡도 : O(n²)

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. Map을 이용한 풀이

• 현재 Index를 value, 해당 보수 값을 key
• 보수 : 보충을 해주는 수
• 반복문을 돌며 현재 수의 보수가 있는지 확인
• 만들 수 없으면 빈 배열을 리턴
• 시간 복잡도 : O(n)

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        /* Map을 이용하여 구현 */
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }

        /* 없을 경우, 빈 배열 리턴 */
        return new int[]{};
    }
}

---