•
문제 설명 : 주어진 nums 에서, diff 만큼 차이나는 삼중항을 몇개 만들 수 있는지 반환
•
풀이 방법
◦
해시테이블 문제이기 때문에, dict를 어떻게 사용할 수 있는지 고민하였다.
▪
dict는 데이터 접근 시, O(1)이기 때문에 이 장점을 살려 문제를 풀어야했다.
◦
이 문제를 해결하기 위해서, 중요한것은 삼중항을 구성하는 요소가 몇번째 인덱스에 있는지 확인하는 부분이 자주 반복된다.
◦
이 확인하는 부분을 dict를 사용하여 시간 복잡도를 줄이는 방식으로 진행했다.
•
시간복잡도 :
•
성공 코드
# O(N + N) -> O(N)
class Solution:
def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
# nums의 각 요소가 몇번째 인덱스에 존재하는지 저장 -> O(N)
index_info_dict = {v: i for i, v in enumerate(nums)}
result = 0
# diff를 사용하여, 두 번째 / 세 번째 값이 nums에 존재하는지 확인한다.
# 만약 둘 다 존재한다면, result를 증가시킨다.
# O(N)
for i, v in enumerate(nums):
second_num_index = index_info_dict.get(v + diff)
third_num_index = index_info_dict.get(v + diff * 2)
if second_num_index and third_num_index:
result += 1
return result
Python
복사