forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKwonNayeon.py
More file actions
52 lines (41 loc) ยท 1.21 KB
/
KwonNayeon.py
File metadata and controls
52 lines (41 loc) ยท 1.21 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
"""
Problem: Two Sum
Constraints:
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists.
<Solution 1>
Time Complexity: O(nยฒ)
- ์ค์ฒฉ ๋ฐ๋ณต๋ฌธ ์ฌ์ฉ
- ์ฒซ ๋ฒ์งธ ๋ฐ๋ณต๋ฌธ: n๋ฒ
- ๊ฐ๊ฐ์ ๋ํ ๋ ๋ฒ์งธ ๋ฐ๋ณต๋ฌธ: n-1, n-2, ... 1๋ฒ
- ์ด ์ฐ์ฐ ํ์: n * (n-1)/2
Space Complexity: O(1)
- ์ถ๊ฐ ๊ณต๊ฐ์ ์ฌ์ฉํ์ง ์์
- result๋ ํญ์ ํฌ๊ธฐ๊ฐ 2๋ก ๊ณ ์ ๋จ
"""
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
result = []
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[j] == target - nums[i]:
return [i, j]
"""
<Solution 2: ํด์ ํ
์ด๋ธ ํ์ฉ>
Time Complexity: O(n)
- ๋ฐฐ์ด์ ํ ๋ฒ๋ง ์ํ
Space Complexity: O(n)
- ์ต์
์ ๊ฒฝ์ฐ ํด์ ํ
์ด๋ธ์ n๊ฐ๋ฅผ ์ ์ฅ
- ์ถ๊ฐ ๊ณต๊ฐ์ด ์
๋ ฅ ํฌ๊ธฐ์ ๋น๋ก
"""
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []