LEETCODE - 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.
------------------------------------------------------------------------------------------------------------------------------

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
Plain Text
복사

Research

Solution을 작성하기 앞서 해당 문제를 풀기 위해 Search Algorithm을 검색해서 사용할 수 있는 게 있을까 확인해 보았습니다만, 적절한 게 없었습니다. 위의 문제에서는 target이 되는 값이 나오는 배열 index를 반환하는 문제이므로 list 내의 두 개의 쌍을 찾는 문제라고 생각하였습니다. 여기서 생각해볼 수 있었던 건 itertools 였습니다.

itertools

먼저, itertools 에서 사용할 수 있는 코드 내용을 확인해보았습니다.

Function	Result Examples
product('ABCD', repeat=2)	AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)	AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)	AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2)	AA AB AC AD BB BC BD CC CD DD

위의 코드 중 두 가지를 테스트 해보았습니다.

import itertools
from typing import List

class Solution:
    def __init__(self) -> None:
        pass

    # Time Limit ---------------------------------------------------------------
    @staticmethod
    def twoSum(nums: List[int], target: int) -> List[int]:
        # itertools.permutations
        # permutations('ABCD', 2) -> AB AC AD BA BC BD CA CB CD DA DB DC
        for i, j in itertools.permutations((i for i in range(len(nums))), 2):
            if (nums[i] + nums[j]) == target:
                return [i, j]

    # Success (Not completely) ---------------------------------------------------------------
    @staticmethod
    def twoSum(nums: List[int], target: int) -> List[int]:
        # itertools.combinations
        # combinations('ABCD', 2) -> AB AC AD BC BD CD
        for i, j in itertools.combinations((i for i in range(len(nums))), 2):
            if (nums[i] + nums[j]) == target:
                return [i, j]
Python
복사

Permutations

permutations는 불필요한 조합(중복)까지 비교하기 때문에 불필요한 연산을 반복합니다. 따라서 Time Limit로 문제를 풀 수 없었습니다.

Combinations

combinations는 해당 문제에서 적절한 조합을 필요한 만큼 가져와 비교할 수 있도록 합니다. 단, Time Limit이거나 가끔 성공하는 케이스로 나타났습니다. 이는 결국 O(n)^2의 연산과 큰 차이가 없기 때문으로 보입니다.

O(n)^2 연산 원인

O(n) : for i, j in ... 반복문

O(n) : itertools로 조합 생성

단, 2번의 itertools로 조합 생성하는 부분은 반복문을 두 번 쓰는 것보다 절반 이상 계산 횟수를 감소될 수 있다고 기대됩니다.

Solution

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
Plain Text
복사

문제의 마지막 라인에 해당 문장이 있습니다. 위 문제를 풀기 위해 O(n)^2의 연산이 아닌 다른 방법을 만들어낼 수 있는지를 물어보고 있습니다. 여기서 다음과 같은 솔루션을 작성하였습니다.

from typing import List

class Solution:
    def __init__(self) -> None:
        pass

    @staticmethod
    def twoSum(nums: List[int], target: int) -> List[int]:
        for i, first in enumerate(nums):
            _tmp = nums.copy()
            first = _tmp.pop(_tmp.index(first))

            try:
                j = _tmp.index(target - first) + 1
                if j:
                    return [i, j]
            except ValueError as e:
                pass
Python
복사

Additional Solution

combinations 활용 방법이 마음에 걸려 조금 더 연구해보았을 때, 다음과 같은 방법으로도 풀이가 가능함을 확인했습니다.

import itertools
from typing import List

class Solution:
    def __init__(self) -> None:
        pass

    @staticmethod
    def twoSum(nums: List[int], target: int) -> List[int]:
        # itertools.combinations
        # combinations('ABCD', 2) -> AB AC AD BC BD CD
        for i, j in itertools.combinations(nums, 2):
            if (i + j) == target:
                a = nums.index(i)
                nums.pop(a)

                return [a, nums.index(j)+1]
Python
복사

이 방법은 combinations object를 이용하여 nums의 조합을 찾아내고, 조합이 맞을 경우 target과 비교하여 index를 찾아 반환하는 방법을 사용하였습니다. 이 방법으로 풀이할 경우 기존 Solution의 방법보다 nums.copy() 연산을 추가적으로 하지 않아도 되므로, 메모리를 보다 절약할 수 있을 것으로 보입니다.