1. 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]

 

계속 자바스크립트  하다가 파이썬 오면 항상 for 돌 때 당황한다

파이썬으로 for 돌 때는 범위를 설정해줘야하는 거 잊지말자.

위 문제에서 중요한 건 for를 인덱스 한번 돌리고 인덱스 +1 로 한번 돌려서 그 두개의 값의 합이 타겟과 같을때를 찾아내면됌

 

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를 두번 사용해서 O(n)2승이라 비효율적이다.

딕셔너리를 사용해서 for를 줄여보면

 

check = {}
for i, num in enumerate(nums):
	if target - num in check:
    	return [check[target-num], i ]
    else:
    	check[num] = i

 

위의 코드처럼 enumerate로 인덱스도 함께 받은 뒤에

타겟에서 배열의 값을 뺀 값이 딕셔너리에 있다면 바로 저장된 인덱스 값을 리턴 시키고

없을 경우에 딕셔너리의 키를 각 배열로 값을 인덱스로 저장한다.