Two Sum

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

풀이

이중 루프

nums를 순회한다. 그 루프 안에서 또 nums를 순회한다.
이때 안쪽 루프는 바깥쪽 루프의 순서가 i라고 했을 때 i + 1부터 배열의 끝까지 순회한다.
바깥쪽 루프에 해당하는 값과 안쪽 루프에 해당하는 값의 합이 target과 같으면
(nums[i] + nums[j] == target)
두 인덱스를 배열로 묶어 반환한다.

코드

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

무려 2535ms

해시 테이블

nums의 값을 key, 인덱스를 value로 하는 해시 테이블을 생성한다.
nums를 순회하며(nums[i]) target - nums[i]의 값이 테이블에 있고, 두 값의 인덱스가 같지 않다면 배열로 묶어 반환한다.

코드

Python

from collections import defaultdict


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numdict = defaultdict()

        for index, num in enumerate(nums):
            numdict[num] = index

        for index, num in enumerate(nums):
            if target - num in numdict and numdict[target - num] != index:
                return [index, numdict[target - num]]

63ms

Java

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numDict = new HashMap<>();
        int[] result = {0, 0};

        for (int i = 0; i < nums.length; i++) {
            numDict.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            if (numDict.containsKey(target - nums[i])) {
                if (i != numDict.get(target - nums[i])) {
                    result[0] = i;
                    result[1] = numDict.get(target - nums[i]);
                    break;
                }
            }
        }

        return result;
    }
}