[LeetCode] 1번문제 - Two Sum

두 숫자 더하기 문제

내용

• 주어진 정수배열 안에서 두 숫자를 더해 target 이 되는 숫자의 index 로 이루어진 배열을 반환하라

조건 및 제약사항

• 주어진 배열에는 정확히 하나의 해답만 존재한다.
• 각 숫자는 한번만 사용 가능하다.

예제

• nums = [2, 7, 11, 15], target = 9
  • result = [0, 1]

코드

import java.util.HashMap;
import java.util.OptionalInt;
import java.util.stream.IntStream;

public class LeetCode1 {
    /**
     * 1. Two Sum
     * https://leetcode.com/problems/two-sum/
     *
     * Example:
     * Given nums = [2, 7, 11, 15], target = 9,
     * Because nums[0] + nums[1] = 2 + 7 = 9,
     * return [0, 1].
     * */

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] result = solution.twoSum2(new int[]{2, 7, 11, 15}, 9);
        System.out.println(result[0] + " / " + result[1]);
    }

    static class Solution {
        // 스트림 사용. 그러나 2중 반복문으로 시간복잡도 조금 더 높음
        public int[] twoSum(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                int temp = i;
                OptionalInt a = IntStream.range(i+1, nums.length)
                        .filter(j -> nums[temp] + nums[j] == target)
                        .findFirst();

                if (a.isPresent()) {
                    return new int[]{i, a.getAsInt()};
                }
            }

            return nums;
        }

        // Hashmap 사용. 정석 방법.
        public int[] twoSum2(int[] nums, int target) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                map.put(target - nums[i], i);
            }
            for (int i = 0; i < nums.length; i++) {
                if (map.containsKey(nums[i])) {
                    return new int[]{i, map.get(nums[i])};
                }
            }
            return nums;
        }
    }
}