[LeetCode] 1. Two Sum - Java

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.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

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

Example 3:

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

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

---

풀이

풀이 과정

숫자들의 배열과 타겟 값이 인자로 주어지고, 배열의 값 중 두 수를 뽑아 더했을 때 타겟값을 만들 수 있는 두 수의 인덱스를 배열로 반환하는 문제이다

정답은 항상 한 가지 경우만 존재하고 정답의 순서는 상관 없으며, 배열 내 같은 값은 두 번 사용할 수 없다

 

두 수의 인덱스 값을 배열로 반환해야 하므로 길이 2짜리 정수 배열을 선언하고
주어진 배열을 탐색하며 탐색 값과 인덱스를 저장해 둘 Map을 선언한다

int[] answer = new int[2];
Map<Integer, Integer> map = new HashMap<>();

 

배열을 탐색하면서 현재 값과 더하여 target을 만들 수 있는 페어 값을 구한다

for(int i = 0; i < nums.length; i++) {
	int pair = target - nums[i]; // 현재 탐색 값에 대한 페어값 ( target - 현재값 )
}

 

Map에 페어 값에 대한 데이터가 저장되어 있다면 페어 값에 대한 인덱스와 현재 탐색중인 인덱스와를 정답 배열에 각각 추가하고 탐색을 종료 및 결과 값을 return한다
페어 값에 대한 데이터가 없는 경우 현재 탐색 값과 인덱스를 Map에 저장하고 탐색을 계속한다

if(map.containsKey(pair)) { // 페어 값이 map에 존재하는 경우
    answer[0] = map.get(pair); // 페어 값에 대한 인덱스와 현재 탐색중인 인덱스를 정답 배열에 추가
    answer[1] = i;
    break;
} else { // 페어값이 없는 경우
    map.put(nums[i], i); // 현재 탐색 값과 인덱스를 map에 저장
}

return answer;

 

최종 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < nums.length; i++) {
            int pair = target - nums[i]; // 현재 탐색 값에 대한 페어값 ( target - 현재값 )
            
            if(map.containsKey(pair)) { // 페어 값이 map에 존재하는 경우
                answer[0] = map.get(pair); // 페어 값에 대한 인덱스와 현재 탐색중인 인덱스를 정답 배열에 추가
                answer[1] = i;
                break;
            } else { // 페어값이 없는 경우
                map.put(nums[i], i); // 현재 탐색 값과 인덱스를 map에 저장
            }
        }
        
        return answer;
    }
}

---