1. Two Sum.md

1. Two Sum

---

출처: https://leetcode.com/problems/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.

• 첫번째 풀이

  combinations를 이용해 모든 숫자들의 comb를 만들고, 그 중 target과 맞는 index를 찾는다.

  그리고 그 index를 사용하여 몇번째와 몇번째 숫자를 더한 것인지 찾는다.

  index - (len(nums) - 1) - (len(nums) -2) .. 해가면서 0 이하가 나오면 stop

  근데 숫자가 19999개인 케이스에서 Memory Exceed가 났다. 이거는 combinations 때문인듯…

  import itertools
  
  class Solution:
      def twoSum(self, nums: List[int], target: int) -> List[int]:
          answer = []
          tmp = list(map(sum, itertools.combinations(nums, 2)))
          #print(tmp)
          tmp = tmp.index(target) + 1
          j = -1
          for i in range(len(nums)-1, 0, -1): # (2, 1, 0)
              j += 1 #(0, 1)
              tmp -= i #(3 - 2) = 1 - 1 = 0
              if (tmp <= 0):
                  answer.append(j) # 1
                  answer.append(len(nums) - 1 + tmp) # 3 - 1 - 0
                  return answer

• 두번째 풀이

  파이썬 메소드를 최대한 사용해서 해봤다.

  import itertools
  
  class Solution:
      def twoSum(self, nums: List[int], target: int) -> List[int]:
          return list(filter(None, map(lambda x:[x[0][0], x[1][0]] if x[0][1] + x[1][1] == target else None, itertools.combinations(enumerate(nums), 2))))[0]

  이거는 ㅋㅋㅋㅋ 어거지로 통과했다 계속 submit하다보면 통과 뜰 때가 있다… 10초가 넘어가면 Time Fail인데 9.5초 정도 걸린다 ㅋㅋ

• 빠른 풀이

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

• 메모리 낮은 풀이

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

• for 문 1개로 풀기

  class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
      for i, x in enumerate(nums):
          if target - x in nums[i + 1:]:
              return sorted([i, nums.index(target - x, i + 1)])