1. 兩數之和
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標。
你可以假設每種輸入只會對應一個答案。但是，陣列中同一個元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]
一、暴力解決，使用雙層for回圈，檢查nums中兩個數的和是否等于target.
好處：簡單
壞處：時間復雜度O(n^2)
# 暴力解決法
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
for x in range(n):
for y in range(x+1, n):
if nums[x] + nums[y] == target:
return x,y
break
else:
continue
二、稍微偷偷懶，使用python自帶的功能，查詢target - nums[i] 是否存在于nums陣列中：
好處：降低時間復雜度O(n)
壞處：還有大佬更厲害
# 偷懶法
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
for x in range(n):
a = target - nums[x]
if a in nums:
y = nums.index(a)
if x == y: # 需要判斷x和y是否相等
continue
else:
return x, y
break
else:
continue
三、大佬處理法，使用dict功能，將nums中的值作為key， 將nums的index作為value。實際：想要使用字典的快速查詢功能，跟使用hash表相似。
好處：降低時間復雜度O(n)
壞處：還有大佬更厲害
# leetcode大佬方法
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
for x in range(n):
a = target - nums[x]
if a in nums:
y = nums.index(a)
if x == y: # 需要判斷x和y是否相等
continue
else:
return x, y
break
else:
continue
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/51287.html
標籤：其他開發語言
上一篇：Python無法保存運行