題目詳細說明請自行到題庫 - 力扣 (LeetCode)搜尋題號
1. 兩數(shù)和
利用數(shù)組的有序,使用兩個指針,一個為l,指向數(shù)組開頭,一個為r,指向數(shù)組結尾;
和大于target時右邊指針左移一個,獲得比當前小的下一個和;
和小于target時左邊指針右移一個,獲得比當前大的下一個和;
循環(huán)條件為 l < r ,循環(huán)結束時就把所有的和都遍歷了一遍, 時間復雜度為O(n);
167. Two Sum II - Input array is sorted
給定一個已按照升序排列的有序數(shù)組停巷，找到兩個數(shù)使得它們相加之和等于目標數(shù)喷好。
函數(shù)應該返回這兩個下標值?index1 和 index2，其中 index1?必須小于?index2。
class Solution:
? ? def twoSum(self, numbers, target):
? ? ? ? """
? ? ? ? :type numbers: List[int]
? ? ? ? :type target: int
? ? ? ? :rtype: List[int]
? ? ? ? """
? ? ? ? if len(numbers) < 2:
? ? ? ? ? ? return None
? ? ? ? l = 0
? ? ? ? r = len(numbers) - 1
? ? ? ? while l < r:
? ? ? ? ? ? s = numbers[l] + numbers[r]
? ? ? ? ? ? if s == target:
? ? ? ? ? ? ? ? #這道題下標從1開始的
? ? ? ? ? ? ? ? return [l + 1, r + 1]
? ? ? ? ? ? elif s < target:
? ? ? ? ? ? ? ? l += 1
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? r -= 1
? ? ? ? return None
2. 擴展, 三數(shù)和
怎么把三數(shù)和轉(zhuǎn)化為兩數(shù)和呢?
我們可以遍歷一次數(shù)組取每一個 nums[i] ,使三數(shù)和等于target相當于
在 nums[ i + 1 : ] 中找兩個下標 l , r 使 nums[l] + nums[r] == target - nums[i]
這樣就轉(zhuǎn)化為兩數(shù)和問題, 時間復雜度為 O(n2) , 注意去除重復答案
給定一個包含?n?個整數(shù)的數(shù)組nums革答，判斷nums中是否存在三個元素?a，b曙强，c 残拐，使得a + b + c =?0 ？找出所有滿足條件且不重復的三元組碟嘴。
注意：答案中不可以包含重復的三元組溪食。
class Solution:
? ? def threeSum(self, nums):
? ? ? ? """
? ? ? ? :type nums: List[int]
? ? ? ? :rtype: List[List[int]]
? ? ? ? """
? ? ? ? #先排序
? ? ? ? nums.sort()
? ? ? ? res = []
? ? ? ? #current標記用于去重
? ? ? ? current = '-1'
? ? ? ? for i, value in enumerate(nums):
? ? ? ? ? ? if current == value:
? ? ? ? ? ? ? ? continue
? ? ? ? ? ? current = value
? ? ? ? ? ? l = i + 1
? ? ? ? ? ? r = len(nums) - 1
? ? ? ? ? ? while l < r:
? ? ? ? ? ? ? ? s = nums[i] + nums[l] + nums[r]
? ? ? ? ? ? ? ? if s == 0:
? ? ? ? ? ? ? ? ? ? res.append([nums[i],nums[l],nums[r]])
? ? ? ? ? ? ? ? ? ? l += 1
? ? ? ? ? ? ? ? ? ? r -= 1
? ? ? ? ? ? ? ? ? ? #去掉重復l
? ? ? ? ? ? ? ? ? ? while l < r and nums[l] == nums[l - 1]:
? ? ? ? ? ? ? ? ? ? ? ? l += 1
? ? ? ? ? ? ? ? ? ? #去掉重復r
? ? ? ? ? ? ? ? ? ? while r > l and nums[r] == nums[r + 1]:
? ? ? ? ? ? ? ? ? ? ? ? r -= 1
? ? ? ? ? ? ? ? elif s < 0:
? ? ? ? ? ? ? ? ? ? l += 1
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? r -= 1
? ? ? ? return res
還有一道4數(shù)和的題目, 思路是一樣的, 再加一層循環(huán), 時間復雜度為 O(n3)
3. 盛水最多容器
用雙指針做,取2個指針,最左 l 和最右 r , 計算兩塊板裝的面積
當 l 的板比 r 的高時 , r -= 1
當 r 的板比 l 的高時,? l += 1
雙指針遍歷相當于求每個寬度下的最大面積, 從中取一個最大值, 時間復雜度為O(n)
給定?n?個非負整數(shù)?a1，a2娜扇，...错沃，an栅组，每個數(shù)代表坐標中的一個點?(i,ai) 。在坐標內(nèi)畫?n?條垂直線枢析，垂直線?i的兩個端點分別為?(i,ai) 和 (i, 0)玉掸。找出其中的兩條線，使得它們與x軸共同構成的容器可以容納最多的水醒叁。
說明：你不能傾斜容器司浪，且n的值至少為 2。
class Solution:
? ? def maxArea(self, height):
? ? ? ? """
? ? ? ? :type height: List[int]
? ? ? ? :rtype: int
? ? ? ? """
? ? ? ? res = 0
? ? ? ? l, r = 0, len(height) - 1
? ? ? ? while l < r:
? ? ? ? ? ? #求面積, 等于寬度乘以 l , r 中高度比較小的那個值
? ? ? ? ? ? res = max(res, (r - l) * min(height[l],height[r]))
? ? ? ? ? ? if height[l] > height[r]:
? ? ? ? ? ? ? ? r -= 1
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? l += 1
? ? ? ? return res
4. 搜尋二維矩陣
使用兩層循環(huán)搜索時間復雜度為O(n2) , 而且沒用到題目給的有序的條件
我們可以假設右上角的值 matrix[x][y] 為初始值, 其中 x = 0 , y = n
當matrix[x][y]? < target時,? 說明 matrix[x] 這一行上的值都比 target 小, x += 1
當matrix[x][y] > target時, 說明matrix在y這一列上的值都比target 大, y -= 1
找到target時返回True, 超出矩陣后返回False? 時間復雜度為 O(m + n)
編寫一個高效的算法來搜索m?x?n矩陣 matrix 中的一個目標值 target把沼。該矩陣具有以下特性：
每行的元素從左到右升序排列啊易。
每列的元素從上到下升序排列。
class Solution:
? ? def searchMatrix(self, matrix, target):
? ? ? ? """
? ? ? ? :type matrix: List[List[int]]
? ? ? ? :type target: int
? ? ? ? :rtype: bool
? ? ? ? """
? ? ? ? #判斷矩陣有沒有值
? ? ? ? x = len(matrix)
? ? ? ? if x == 0:
? ? ? ? ? ? return False
? ? ? ? y = len(matrix[0])
? ? ? ? if y == 0:
? ? ? ? ? ? return False
? ? ? ? #y取最后一列的下標
? ? ? ? y -= 1
? ? ? ? i = 0
? ? ? ? while i < x and y >= 0:
? ? ? ? ? ? if matrix[i][y] < target:
? ? ? ? ? ? ? ? i += 1
? ? ? ? ? ? elif matrix[i][y] > target:
? ? ? ? ? ? ? ? y -= 1
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? return True
? ? ? ? return False
