[Blind75] Two Sum

problem

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.

blind 75 그 유명한 leetcode 문제집의 대망의 첫번째 문제이다. 애초에 이런 것이 존재하는 줄 모르고 있다가. DaleSeo 님의 문제 스터디 모집을 보고 알았다. 현재는 모두 마감되었고 2024.08에 다시 스터디원을 모집한다고 하니 그때 기회가 있다면 지원해 보도록 하자.

python

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

처음에는 brute force 방식으로 풀 수 있다. 단 하나의 그리고 하나의 답만 이 존재한다는 조건이 있기 때문에 가능한 방법이다. 만약 답이 여러 개가 있다 거나, 또 그 답을 골라내야 하는 조건이 따로 존재하는 경우에는 brute force 방식은 그다지 효율적이지 않을 수 있다.

from collections import deque
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

이것은 한참 deque에 빠져있을 때 풀었던 풀이이다. two pointer처럼 계속 뒤로 옮겨가면서 첫 번째 걸리는 놈을 찾는 방식이다. 시간 복잡도는 해당 방식이 굳이 이전의 brute force 방식보다 좋지는 못하다. 하지만 해당 방식도 쓰일 경우가 있을 것이다.

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[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {};
    }
}

크게 처음의 brute force와 다를 게 없는 코드이다. new만 주의하자.

javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return [i, j];
            }
        }
    }
};

역시 다를게 없다. 다만 java와 return 부분에서 미리 선언하지 않았던 경우에는 java는 new를 사용해줘야하고, javascript에서는 무지성으로 선언하면서 동시에 return해주면 된다. 역시 type에 민감하게 굴지 않는 javascript의 모습을 볼 수 있다.