[LeetCode/Easy] 1. Two Sum

1. Two Sum

첫 번째 시도

두 번째 시도

Testcase 통과한다고 해서 Submit 하면 안 된다 ㅠㅠ 제한시간 내에 Edge case를 생각해보고 그마저도 통과하면 Submit 하자!

내 풀이 vs. 답안 풀이

---

	내 풀이	답안 풀이
$O(n^2)$보다 적은 Time complexity를 고려한 구현	for문 2개 하면 $O(n^2)$이 나오니 조합(combination)으로 먼저 구해야겠다 생각했지만 결국은 for문에 while문으로 구현함으로써 $O(n^2)$이 됨.. -> 내 풀이의 time complexity 구하는 연습을 많이 해야겠다.	Hash Table 내가 필요한 건 index고 알고 있는 건 숫자이므로 key는 nums 원소, value는 index여야 함. -> 내가 필요한게 뭐고 알고 있는게 뭔지 잘 정의하고 구현하기!
문제를 좀 더 쉽게 푸는 방법? 문제를 단순화시키기	result = nums[i] + nums[i+j] 알아내야 하는 것이 2개라고 생각했음..	cur(현재 위치) + x = target cur과 target은 알고 있으니 내가 알아내야 하는 것은 x = target - cur -> 위와 마찬가지로, 내가 필요한게 뭐고 알고 있는게 뭔지 잘 정의하고 구현하기!

내 답안

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_len = len(nums)
        if nums_len == 2:
            return [0,1]
        else:
            for i in range(nums_len):
                j = 1
                while i + j != nums_len:
                    result = nums[i] + nums[i+j]
                    if result == target:
                        return [i,i+j]
                    else:
                        j += 1

012

문제 풀면서 작성한 메모

답안 예시

Approach 1: Brute Force

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[j] == target - nums[i]:
                    return [i, j]

• Time complexity: $O(n^2)$
• Space complexity: $O(1)$

while문에 j 초기화하고 +1씩 더할거면 for문을 써야지.. 왜 뭐가 다르다고 while문을 썼는지 ㅠㅠ

Approach 2: Two-pass Hash Table

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            hashmap[nums[i]] = i
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap and hashmap[complement] != i:
                return [i, hashmap[complement]]

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Approach 3: One-pass Hash Table

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i

• Time complexity: $O(n)$
• Space complexity: $O(n)$

개념 정리

---

해시맵(Hash Map), 해시 테이블(Hash Table) (>>출처)

• Key-value pairs를 저장하는 data structure가 필요하면 딕셔너리 떠올리기!
  (Python의 해시맵으로 구성된 자료구조는 딕셔너리이기 때문)
• 특징
  • 순차적으로 데이터를 저장하지 않습니다.
  • Key를 통해서 Value값을 얻습니다.
  • Value값은 중복가능 하지만 Key는 중복될 수 없습니다.
  • 수정 가능합니다.(mutable)