[Leetcode 01] 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?

 

Brute Force

class Solution(object):            
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 모든 페어에 대해 다 더해보면 O(n^2)
        # Runtime: 3963 ms,
        # faster than 22.61% of Python online submissions for Two Sum.
        # Memory Usage: 14.3 MB,
        # less than 44.38% of Python online submissions for Two Sum.
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

가장 쉽게 접근하는 방법. 그냥 다 더해보기.

 

Sorting?

복잡도를 줄일 때 할 수 있는 생각은 소팅을 하거나, Hashmap을 쓰는 것.

좋게 개선하려고 생각하다가 소팅에 꽂혀서 아래를 생각.

class Solution(object):
    def find_pair_target_sum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [nums[i], nums[j]]
                elif nums[i] + nums[j] > target:
                    break
                
                
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 소팅한 다음에, 합이 target인 짝을 찾고 그걸 원래 인덱스에서 찾으면
        # O(nlogn) + O(n^2) + O(n)
        
        # O(nlogn)
        new_nums = sorted(nums)
        # O(n^2)
        pair = self.find_pair_target_sum(new_nums, target)
        # O(n)
        answer = []
        for i in range(len(nums)):
            if nums[i] in pair:
                answer.append(i)
        return answer

 

Hashmap

class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       seen = {}
       for i, value in enumerate(nums):
           remaining = target - nums[i]
           
           if remaining in seen:
               return [i, seen[remaining]]
            
           seen[value] = i

합이 target인 걸 찾으면 되는 거니까!

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        // In case there is no solution, we'll just return null
        return null;
    }
}

전엔 hashmap 써서 풀었던 제출 기록이 있는데, 다시 푸니까 이걸 바로 떠올리지 못했다.

 

딱 봤을 때 쉽게 푸는 건 O(n^2).

O(n)에 할 수 있는 문제.

 

 

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode