1. Two Sum

Description

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 <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than 𝑂(𝑛²) time complexity?

💡 Hint 1:
A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.

💡 Hint 2:
So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

💡 Hint 3:
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

Submitted Code

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):                  # i = first index
            for j in range(i+1, len(nums)):         # j = second index
                if nums[i] + nums[j] == target:
                    return [i, j]

Time complexity: 𝑂(𝑛²) ← 한 번 루프를 도는데 O(n) * 중첩된 for문 순회 O(n)
Space complexity: 𝑂(1)

Brute Force를 사용하여 가능한 모든 쌍의 조합을 처음부터 하나씩 대입하여 결과를 얻는 방법
가장 간단하면서 100% 정확도를 보장하지만 비효율적인 알고리즘이다.

Other Solutions

Editorial

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i
        # Return an empty list if no solution is found
        return []

Time complexity: 𝑂(𝑛)
Space complexity: 𝑂(𝑛)

One-pass Hash Table 사용
해시테이블에 각 요소와 그에 해당하는 인덱스를 저장한다.

nums = [4, -2, 5, 0, 6, 3, 2, 7]
target = 1

current_value + x = target
∴ x = target - current_value
∴ x = 1 - current_value

get x value	map (save index)
x = 1 - 4 = -3 (not in nums)	4 → 0
x = 1 - (-2) = 3 (not in nums)	-2 → 1
x = 1 - 5 = -1 (not in nums)	5 → 2
x = 1 - 0 = 1 (not in nums)	0 → 3
x = 1 - 6 = -5 (not in nums)	6 → 4
x = 1 - 3 = -2 (in nums)	3 → 5

1 = -2 + 3
∴ target = -2 + 3

output = [5, 1]

2nd

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        pair_idx = {}                               # 값: 인덱스 를 저장하는 해시맵

        for i, num in enumerate(nums):              # nums 리스트의 인덱스와 값 가져오기
            if target - num in pair_idx:            # 현재 숫자와 더하면 답이 되는 숫자가 딕셔너리에 있다면
                return [i, pair_idx[target - num]]    # 해당 키(값)의 인덱스 반환
            pair_idx[num] = i                       # 딕셔너리에 없다면 현재 숫자와 인덱스를 딕셔너리에 저장