forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEgonD3V.py
More file actions
88 lines (71 loc) ยท 2.7 KB
/
EgonD3V.py
File metadata and controls
88 lines (71 loc) ยท 2.7 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
from typing import List
from unittest import TestCase, main
from collections import defaultdict
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
return self.solveWithMemoization(nums, target)
"""
Runtime: 3762 ms (Beats 5.00%)
Time Complexity: O(n ** 2)
> ํฌ๊ธฐ๊ฐ n์ธ nums ๋ฐฐ์ด์ 2์ค์ผ๋ก ์กฐํํ๋ฏ๋ก O(n ** 2)
Memory: 17.42 MB (Beats 61.58%)
Space Complexity: O(1)
> ๋ฑํ ์ ์ฅํ๋ ๋ณ์ ์์ (๋ฐํํ๋ list ์ ์ธ)
"""
def solveWithBruteForce(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(len(nums)):
if i != j and nums[i] + nums[j] == target:
return [i, j]
"""
Runtime: 52 ms (Beats 89.73%)
Time Complexity: O(n)
1. nums ๋ฐฐ์ด์ ๋๋ฉฐ idx๋ฅผ ์ ์ฅํ๋ dict ์์ฑ์ O(n)
2. ์ฒซ ์ซ์๋ฅผ ์ ํํ๊ธฐ ์ํด len(nums)๋ฅผ for๋ฌธ์ผ๋ก ์กฐํํ๋๋ฐ O(n)
> O(2n) ~= O(n)
Memory: 19.96 MB (Beats 8.42%)
Space Complexity: O(n)
- ํฌ๊ธฐ๊ฐ n์ธ defaultdict ๋ณ์ ์ฌ์ฉ
"""
def solveWithMemoization(self, nums: List[int], target: int) -> List[int]:
num_to_idx_dict = defaultdict(list)
for idx, num in enumerate(nums):
num_to_idx_dict[num].append(idx)
for i in range(len(nums)):
first_num = nums[i]
second_num = target - nums[i]
if first_num != second_num:
if not (len(num_to_idx_dict[first_num]) and len(num_to_idx_dict[second_num])):
continue
else:
if not (2 <= len(num_to_idx_dict[first_num])):
continue
first_idx = num_to_idx_dict[first_num].pop()
second_idx = num_to_idx_dict[second_num].pop()
if first_num != second_num:
return [first_idx, second_idx]
else:
return [second_idx, first_idx]
class _LeetCodeTestCases(TestCase):
def test_1(self):
nums = [2, 7, 11, 15]
target = 9
output = [0, 1]
self.assertEqual(Solution.twoSum(Solution(), nums, target), output)
def test_2(self):
nums = [3,2,4]
target = 6
output = [1, 2]
self.assertEqual(Solution.twoSum(Solution(), nums, target), output)
def test_3(self):
nums = [3, 3]
target = 6
output = [0, 1]
self.assertEqual(Solution.twoSum(Solution(), nums, target), output)
def test_4(self):
nums = [3, 2, 3]
target = 6
output = [0, 2]
self.assertEqual(Solution.twoSum(Solution(), nums, target), output)
if __name__ == '__main__':
main()