1.TwoSum

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]

• 문제 풀이

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

• 문제 분석
  - 간단하게 생각해서 Bruteforce로 구성했음 전체 개수가 10^4개라 brute force해도 된다고 생각
  • O(n^2)
• 개선 코드

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

• 개선 방안
  - 두개의 합을 구하는 것이기 때문에 Dictionary의 key, value를 이용하면 구할 수 있다.
  • dictionary에 존재하지않으면 target에서 현재 value를 뺀 값을 key로 하고 index를 value로 넣는다.
  • dictionary에 존재할 경우, 내 index와 dictionary의 index를 return한다.
  • 순서는 상관 X
  • O(n)으로 개선