Two Sum - tanakakenji/Rinko GitHub Wiki
ๅ้ก:
ๆดๆฐใฎ้
ๅ nums ใจๆดๆฐใฎ target ใไธใใใใใจใใใใใใ่ถณใๅใใใใจ target ใซใชใใใใช2ใคใฎๆฐใฎใคใณใใใฏในใ่ฟใใฆใใ ใใใ
ๅๅ ฅๅใซใฏๆญฃ็ขบใซ1ใคใฎ่งฃใๅญๅจใใใจไปฎๅฎใใฆใใใๅใ่ฆ็ด ใ2ๅไฝฟ็จใใใใจใฏใงใใพใใใ
็ญใใฏไปปๆใฎ้ ๅบใง่ฟใใใจใใงใใพใใ
ไพ:
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] == 9 ใชใฎใงใ[0, 1] ใ่ฟใใพใใ
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
ๅถ็ด:
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
ๆๅนใช็ญใใฏ1ใคใ ใๅญๅจใใพใใ
ใใฉใญใผใขใใ: O(n^2) ๆชๆบใฎๆ้่จ็ฎ้ใๆใคใขใซใดใชใบใ ใ่ๆกใงใใพใใ๏ผ
ๅ็ญใจ่งฃ่ชฌ:
ใใฎๅ้กใฏใ้ ๅใฎไธญใใ2ใคใฎๆฐใ่ฆใคใใใใใใฎๅ่จใๆๅฎใใใใฟใผใฒใใๅคใซใชใใใใซใใๅคๅ ธ็ใชใTwo Sumใๅ้กใงใใ
ๅบๆฌ็ใชใขใใญใผใ (Brute Force):
ๆใ็ฐกๅใชใขใใญใผใใฏใ้ ๅๅ ใฎใในใฆใฎๅฏ่ฝใชใใขใ่ฉฆใใใจใงใใ
def twoSum_bruteforce(nums: list[int], target: int) -> list[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return [] # ่งฃใ่ฆใคใใใชใๅ ดๅใฏ็ฉบใฎใชในใใ่ฟใ (ใใ ใใๅ้กๆใงใฏๅฟ
ใ่งฃใๅญๅจใใใจใใใฆใใพใ)
# ไพ
nums1 = [2,7,11,15]
target1 = 9
print(twoSum_bruteforce(nums1, target1)) # Output: [0, 1]
nums2 = [3,2,4]
target2 = 6
print(twoSum_bruteforce(nums2, target2)) # Output: [1, 2]
nums3 = [3,3]
target3 = 6
print(twoSum_bruteforce(nums3, target3)) # Output: [0, 1]
ๆ้่จ็ฎ้: ใใฎใขใใญใผใใงใฏใใในใใใใใซใผใใไฝฟ็จใใฆใใใใใๆ้่จ็ฎ้ใฏ O(n^2) ใงใใ
ๅน็็ใชใขใใญใผใ (ใใใทใฅใใใใไฝฟ็จ):
ใใๅน็็ใชใขใใญใผใใฏใใใใทใฅใใใ (่พๆธ) ใไฝฟ็จใใใใจใงใใ้ ๅใไธๅบฆใ ใๅๅพฉๅฆ็ใใชใใใๅๆฐๅคใซๅฏพใใฆใใฟใผใฒใใๅคใซ้ใใใใใซๅฟ ่ฆใช่ฃๆฐใใใงใซใใใทใฅใใใใซๅญๅจใใใใฉใใใ็ขบ่ชใใพใใ
def twoSum_hashmap(nums: list[int], target: int) -> list[int]:
seen = {} # ๆฐๅคใจใใฎใคใณใใใฏในใๆ ผ็ดใใใใใทใฅใใใ
for index, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], index]
seen[num] = index
return [] # ่งฃใ่ฆใคใใใชใๅ ดๅใฏ็ฉบใฎใชในใใ่ฟใ (ใใ ใใๅ้กๆใงใฏๅฟ
ใ่งฃใๅญๅจใใใจใใใฆใใพใ)
# ไพ
nums1 = [2,7,11,15]
target1 = 9
print(twoSum_hashmap(nums1, target1)) # Output: [0, 1]
nums2 = [3,2,4]
target2 = 6
print(twoSum_hashmap(nums2, target2)) # Output: [1, 2]
nums3 = [3,3]
target3 = 6
print(twoSum_hashmap(nums3, target3)) # Output: [0, 1]
่งฃ่ชฌ:
-
ใใใทใฅใใใ
seenใฎๅๆๅ: ็ฉบใฎ่พๆธseenใไฝๆใใพใใใใฎ่พๆธใฏใใใงใซๅๅพฉๅฆ็ใใๆฐๅคใจใใฎใคใณใใใฏในใๆ ผ็ดใใใใใซไฝฟ็จใใใพใใ -
้ ๅใฎๅๅพฉๅฆ็:
enumerateใไฝฟ็จใใฆใ้ ๅnumsใฎใคใณใใใฏในใจๅคใๅๆใซๅๅพฉๅฆ็ใใพใใ -
่ฃๆฐใฎ่จ็ฎ: ็พๅจใฎๆฐๅค
numใซๅฏพใใฆใใฟใผใฒใใๅคใซ้ใใใใใซๅฟ ่ฆใช่ฃๆฐcomplementใ่จ็ฎใใพใ (complement = target - num)ใ -
่ฃๆฐใฎๅญๅจ็ขบ่ช: ใใใทใฅใใใ
seenใซcomplementใใญใผใจใใฆๅญๅจใใใใฉใใใ็ขบ่ชใใพใใ- ๅญๅจใใๅ ดๅใใใใฏไปฅๅใซๅๅพฉๅฆ็ใใๆฐๅคใฎไธญใซใ็พๅจใฎๆฐๅคใจ่ถณใๅใใใใจ
targetใซใชใๆฐๅคใๅญๅจใใใใจใๆๅณใใพใใ - ใใใทใฅใใใใใ่ฃๆฐใฎใคใณใใใฏในใๅๅพใใ็พๅจใฎๆฐๅคใฎใคใณใใใฏในใจใจใใซ่ฟใใพใใ
- ๅญๅจใใๅ ดๅใใใใฏไปฅๅใซๅๅพฉๅฆ็ใใๆฐๅคใฎไธญใซใ็พๅจใฎๆฐๅคใจ่ถณใๅใใใใจ
-
ใใใทใฅใใใใธใฎ่ฟฝๅ : ่ฃๆฐใใใใทใฅใใใใซ่ฆใคใใใชใๅ ดๅใ็พๅจใฎๆฐๅค
numใจใใฎใคใณใใใฏในใใใใทใฅใใใseenใซ่ฟฝๅ ใใพใใใใใซใใใๅพ็ถใฎๅๅพฉๅฆ็ใงใใฎๆฐๅคใ่ฃๆฐใจใใฆๅฟ ่ฆใซใชใฃใๅ ดๅใซใๅน็็ใซๆค็ดขใงใใพใใ
ๆ้่จ็ฎ้: ใใฎใขใใญใผใใงใฏใ้ ๅใไธๅบฆใ ใๅๅพฉๅฆ็ใใใใใทใฅใใใใธใฎใขใฏใปในใฏๅนณๅใใฆ O(1) ใฎๆ้ใง่กใใใใใใๅ จไฝใฎๆ้่จ็ฎ้ใฏ O(n) ใงใใ
็ฉบ้่จ็ฎ้: ใใใทใฅใใใ seen ใซใฏใๆๆชใฎๅ ดๅใ้
ๅใฎใในใฆใฎ่ฆ็ด ใๆ ผ็ดใใใๅฏ่ฝๆงใใใใใใ็ฉบ้่จ็ฎ้ใฏ O(n) ใงใใ
ใใฉใญใผใขใใใธใฎๅ็ญ:
ใฏใใๅน็็ใชใขใใญใผใ (ใใใทใฅใใใใไฝฟ็จ) ใฏ O(n) ใฎๆ้่จ็ฎ้ใๆใฃใฆใใใO(n^2) ๆชๆบใงใใใใใฏใใใฉใญใผใขใใใฎ่ฆๆฑใๆบใใใฆใใพใใ
ใใฎใใใทใฅใใใใไฝฟ็จใใใขใใญใผใใฏใTwo Sum ๅ้กใฎๆจๆบ็ใชๅน็็ใช่งฃๆณใจใใฆๅบใ็ฅใใใฆใใพใใ