[LeetCode] 1. Two Sum

1. 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.

정수 배열 nums와 정수 target이 주어질 때, 합계가 target이 되는 두 숫자의 인덱스를 반환하십시오.
각 입력에는 정확히 하나의 해결책이 있다고 가정하며, 같은 요소를 두 번 사용할 수 없습니다.
답변은 어떤 순서로 반환해도 상관없습니다.

Example

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Input: nums = [3,2,4], target = 6
Output: [1,2]

---

1. 문제 요구사항 분석

정수로 이루어진 array와 target이 주어졌을 때, 배열 내에서 두 요소를 더해 target이 되는 요소들의 인덱스를 찾는 문제

 

2. 접근 전략

😭 직관적인 방법: 이중 for문을 사용해 쌍 더하기 => 시간 복잡도가 O(n^2)이 되어 배열의 크기가 커지면 비효율적

---

😄 해시맵 사용: target에서 현재 값을 빼고 두 수의 합이 특정 값이 되는 쌍이 있는지 확인 => 시간 복잡도 O(n)

 

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

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 예외/경계 조건 처리: 배열이 비어있거나 요소가 2개 미만인 경우
        if (nums == null || nums.length < 2) {
            return new int[]{};
        }

        // 값과 인덱스를 저장할 해시맵 생성
        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 new int[]{};
    }
}

 

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

Two Sum - LeetCode