[TIL] Code Kata 1

import timeit

start = timeit.default_timer()

# solution 1

 def two_sum(nums, target):
     answer = []
     for i in range(len(nums)):
         for j in range(i+1,len(nums)):
             if nums[i] + nums[j] == target:
                 answer.append(i)
                 answer.append(j)
                 break

     return answer
     
     
# solution 2

def two_sum(num,target):
    for i in num:
        val1 = target - i
        if val1 in num:
            a = num.index(i)
            b = num.index(val1)
            return [a,b]

two_sum([1,2,3,4,5,6,7,8,9],17)

end = timeit.default_timer()

print(end-start)

1번처럼 이중 포문으로 풀고나서 조금 더 효율적인 코드는 없을까를 생각해보다가 for문을 한번만 쓰고 풀수 있을거 같다는 생각이 들었다. 주어진 target을 이용해서 한번 풀어보려고 노력했다. 리스트 값들 중에 한개를 뽑아서 target 에서 뺀 뒤 in 을 사용해서 값을 찾는 방법이였다. 코드 반복이 줄여 효율적인 코드라고 생각했지만 리스트에서는 in 이 O(n)의 시간 복잡도를 가진다는것을 알게 되었다. 결국 in 으로 인해 하나하나 값들을 확인하면서 값을 찾아내므로 내가 원하는 효율적인 코드가 아니였다.
오히려 이중포문보다 더 늦게 결과가 도출되었다.

1번 1.30초 , 2번 4.37초 둘다 테스트는 통과한다.