HashTable - Two Sum (과거인덱스, 지금인덱스)

def solution(nums, target): #시간 복잡도 O(n^2)
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if nums[i]+nums[j]==target:
                return True
    else:
      return False






def solution(nums, target):
    nums.sort() #O(nlogn) 정렬의 시간복잡도
    x = 0
    y = len(nums)-1
    while(x<y): #O(n): 원소가 n개인경우 n번 접근
      if nums[x]+nums[y]<target:
            x=x+1  
      if nums[x]+nums[y]>target:
            y=y-1  
      if nums[x]+nums[y]==target:
          return True
    return False




#원하는 값을 key에 넣는다.
#미완성틀린 풀이임 
def solution(nums, target):
    dict = {}
    for x in nums:    #for문 : O(n)
        dict[x]=1     #O(1)  참고: 1은 의미없는 임의의 값
    

    for v in nums:  #for문 : O(n)
        needed_number = target -v

        if needed_number == v:
            continue

        if needed_number in dict:        #in연산자 시간복잡도 O(1) : 해시함수로 key에 한번에 접근
        # if needed_number in nums:      #in연산자 시간복잡도 O(n) : 리스트에서 모든 요소를 살펴봄
        
            return True
    
    else:
        return False
    


#HashTable이용
def solution(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        needed_number = target - num
        if needed_number in seen:
            return [seen[needed_number], i]  #seen[needed_number] : 과거의 인덱스,  i는 지금 index 
        seen[num] = i
    return None

nums = [ 4, 1, 9, 7, 5, 16]
target = 14
print(solution(nums, target))

nums = [2, 1, 5, 7] #2를 두번 사용하는 문제 
target = 4
print(solution(nums, target))

#nums리스트의 요소가 동일한 숫자일지라도 각각의 고유 번호를 부여한다. 
nums = [3, 3] #같은 원소를 두번 사용하지 않았음 정답은 True가 나와야 된다.
target = 6
print(solution(nums, target))