[leetcode]1. two-sum

문제 설명

주어진 리스트에서 target을 만들 수 있는 두 숫자를 골라서 그 숫자의 인덱스를 반환하는 문제이다.

풀이 1

가능한 경우의 수는 한 가지라고 주어져있기 때문에 처음에는 for문을 돌면서
target을 만족하는 조합이 나오면 인덱스를 반환하는 경우를 생각했다.

확실히 2중 for문이기 때문에 주어진 리스트가 길수록 runtime이 길어진다.

풀이 2

다음으로 생각해낸 방법은 python 내장 함수를 사용하는 것이다.
리스트에서 숫자를 2개씩 묶는 경우의 수를 리스트로 만들어서 for문을 도는 횟수를 줄이는 것이다.

위와 같이 작성한 경우 리스트 길이가 짧을 때는 맞는 값을 반환하지만 길이가 길어지면
memory limit exceeded 에러가 뜬다

풀이 3

다음으로 hash table을 사용해보자
파이썬에서는 dictionary를 활용하면 된다.
우선 dict의 key는 list 데이터, value는 index로 설정한다.
이때 중복 key가 있으면 마지막 인덱스 값이 저장되므로 주의하자

또한 nums2가 my_dict안에 있을 때 자신을 찾을 수 있으니 인덱스가 다르다는 조건을 넣어줘야한다.