[LeetCode] 1. two_sum (Easy) 2023/4/29

문제 제목	정답률	난이도
1. two-sum	49.8%	Easy

Two Sum - LeetCode

 

문제요약

타깃 숫자가 주어졌을 때 배열 원소의 합으로 나타낼 수 있다면 인덱스를 반환해라

조건 1) 정수형 타깃 숫자와 정수형 배열이 주어진다

조건 2) 같은 원소를 두 번 사용하는 것은 불가하며 각 문제에 정확히 하나의 답이 존재한다고 생각해라

 

 

생각했던 풀이 1. Brute-Froce(모든 가능한 경우를 하나씩 대입) -> for 문장 두 개 사용해서 구하기 - (시간복잡도 $O(n^{2})$)

생각했던 풀이 2. 정답-첫번째값이 리스트에 있는지 확인 -> for과 in을 사용해서 풀이 - (시간복잡도 $O(n^{2})$)

생각했던 풀이 3. 정답-첫번째값의 리스트 key 값을 조회 - (시간복잡도 $O(n)$)

생각했던 풀이 4. 투 포인터 이용 -> sort() 함수 이용해서 정렬한 뒤 사용하면 되나 인덱스가 엉망이 되기 때문에 추천하지 않는다고 함

 

 

풀이 2 (567 ms)

정답-첫 번째 값이 리스트에 있는지 확인

 

Step1. 첫번째 원소값을 뺀 나머지 값이 리스트에 있는지 확인 -> for, in 함수

- (시간복잡도 $O(n^2)$)

 

리스트의 인덱스와 값에 모두 접근할 수 있게 하는 함수

enumerate(list)

 

 

Setp2. 해당 값의 인덱스 반환

 

리스트에 해당 값이 있는지 확인하는 함수	list.index(value)
중복되는 원소들의 인덱스 모두 찾는 함수	numpy_array=numpy.array(list) numpy.where(numpy_array==값)[0]

 

 

구현 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for first_index, first_num in enumerate(nums):
            second_num=target-first_num
            if(second_num in nums[first_index+1:]):
                return [first_index, nums[first_index+1:].index(second_num)+(first_index+1)]

 

 

풀이3 (82ms)

정답-첫 번째 값의 리스트 key 값을 조회 -> 딕셔너리 이용

 

Step1. 첫번째 원소값을 뺀 나머지 값이 딕셔너리에 있는지 확인 -> for, dict[] 함수 이용

- (시간복잡도 $O(n)$)

 

 

Setp2. 해당 값(딕셔너리의 key)의 인덱스(딕셔너리의 value) 반환

 

 

구현

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dict={}
        for index, num in enumerate(nums):
            nums_dict[num]=index
        for first_index, first_num in enumerate(nums):
            second_num=target-first_num
            if(second_num in nums_dict and first_index!=nums_dict[second_num]):
                return [first_index, nums_dict[second_num]]