twoSum

Surdarla

Dec 04 Mon 14:38, 2023

1 min read

문제

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.

constraints

• 2 <= nums.length <= 10^4

• -10^9 <= nums[i] <= 10^9

think

\(O(n^2)\)의 이중 for 문을 돌면은 brute force로 완전탐색을 하면서 풀 수 있긴 하다. 하지만 문제의 제한에서 nums 리스트의 크기가 매우 클 수 있다는 점과 하나의 요소의 크기도 매우 클 수 있다는 점이 존재하는 걸로 봐서는 좋은 풀이로는 보이지 않는다. O(n)의 시간복잡도로 줄이는 방법에 대한 고민이 필요하다.

hash map에 대해서 생각해볼 필요가 있는 문제이다.

python

import sys, os

problem_num = "twoSum"

path = os.getcwd() + f"\\txt\\{problem_num}" + ".txt"
sys.stdin = open(path, "r")
input = sys.stdin.readline

nums = list(map(int, input().split()))
target = int(input())

from collections import deque
from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        popidx = 0
        nums = deque(nums)
        while nums:
            start = nums.popleft()
            popidx += 1
            for idx, i in enumerate(nums):
                if start + i == target:
                    result = [popidx - 1, idx + popidx]
                    break
        return result

answer = Solution().twoSum(nums, target)
answer

[0, 1]

javascript

Listing 13 nodejs code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

var twoSum = function (nums, target) {
    let popIndex = 0;
    while (nums.length > 0) {
        let start = nums.shift();
        popIndex++;
        for (let idx = 0; idx < nums.length; idx++) {
            if (start + nums[idx] === target) {
                result = [popIndex - 1, idx + popIndex];
                break;
            }
        }
    }
    return result;
};

Java

class Solution {
    public int[] twoSum(int[] nums, int target){
        for (int i=0; i< nums.length;i++){
            for (int j = i+1;j<nums.length;j++){
                if (nums[j] == target-nums[i]){
                    return new int[] {i,j};
                }
            }
        }
        return null;
    }
}