LeetCode 第 1個問題：兩數之和
題目描述
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，你不能重復利用這個陣列中同樣的元素，
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]
暴力搜索演算法
解題思路：利用兩個回圈解決
代碼
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[i] + nums[j] == target:
return [i,j]
結果and總結
運行時間：6132ms ???? 記憶體消耗：14MB
此處用到了兩個回圈
利用python中list相關函式解決
方法一：
解題思路：
找到num2 == target - num1 是否在list中，然后運用兩個方法：
- num2 in nums 回傳true說明成功
- nums.index(num2) 查找num2的索引
代碼
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums):
num1 = nums[i]
num2 = target - num1
if num2 in nums:
#如果num2=num1，且在nums中出現了一次，說明找到num1本身，
if(num1 == num2) & (nums.count(num2)==1):
continue
return[i,nums.index(num2,i+1)] #index(num2,i+1)是從num1后的序列找num2位置
結果and總結
運行時間：1148ms ???? 記憶體消耗：14MB
此處用到了一個回圈
方法二：
解題思路：在方法一的基礎上，num2的查找不需要每次從nums查找一遍，可以按照切片的思想從num1之前或者之后查找就行，這次從num1之前找.
代碼
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(1,len(nums)):
temp = nums[:i]
num1 = target - nums[i]
if num1 in temp:
j = temp.index(num1)
return[j,i]
結果and總結
運行時間：408ms ???? 記憶體消耗：13.8MB
這個演算法先找到串列[2,7,11,15]中的7，再找到2；所以return[j,i]時先回傳j,再回傳i
利用字典解決
方法一：
解題思路：利用字典模擬哈希求解，遍歷串列同時查字典
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dct = {}
for i, n in enumerate(nums):
if target-n in dct:
return [dct[target - n], i]
dct[n] = i #構造字典
結果and總結
運行時間：48ms ???? 記憶體消耗：14.6MB
- 這個演算法先用串列中的[2,7,11,15]，9-2=7在字典中查找7，但此時字典是空的，把2存入字典；
- 然后再用9-7=2在字典中查找，此時字典中已存入了一個2，找到了7和2的位置；
- 在回傳時
return[dct[target - n],i]，此時target - n為9-7=2，故先回傳2的位置，再回傳7的位置
小結
利用字典解決該問題最簡單，遍歷串列同時查字典，但也消耗了一定記憶體
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/190203.html
標籤：python
上一篇：《零基礎看得懂的C語言入門教程 》——（七）C語言的回圈分分鐘上手
下一篇：Anaconda常用命令小結