引言
前文介紹了順序表的基本操作，本文主要來分析有關順序表的經典編程題目，
順序表例題
兩數之和
問題來源：
力扣：1. 兩數之和
問題簡述：
題目給定了一個target，要求在這個整數陣列中找出兩個整數的和恰好等于target，并回傳整數的下標，
問題分析：
最簡單的實作方法是列舉法，利用雙層回圈查找哪兩個整數恰好和為target，只要查找到就回傳結果，但這樣做會使得平均時間復雜度為O(N^2)，效率較低，
正確的做法為設定一個哈希表，利用哈希表預先存盤陣列中元素的值和索引，然后線性掃描整個陣列，如果發現哈希表中存在target-nums[i]的鍵且值不等于i則停止掃描，回傳結果，
代碼：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
Hashtable = {}
for i,j in enumerate(nums):
Hashtable[j] = i
for k in range(len(nums)):
s = Hashtable.get(target - nums[k])
if s != k and s is not None:
return [k, s]
洗掉排序陣列中的重復項
問題來源：
力扣：26. 洗掉排序陣列中的重復項
問題簡述：
給定一個排序陣列，要求使用O(1)空間原地將重復項洗掉，并回傳洗掉重復項后陣列的長度，
問題分析：
本題難點在于將空間復雜度限制在O(1)層次，因此哈希計數、線性掃描等方法在此處無法使用，
由于題目中告知不需要考慮新長度后陣列中的元素，因此我們可以考慮采用雙指標（滑動視窗），將要洗掉的元素覆寫，即可實作重復項洗掉操作，
代碼
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
else:
a, b = 0, 1
while b < len(nums):
while b < len(nums) and nums[b] == nums[a]:
b += 1
if b < len(nums):
a += 1
nums[a] = nums[b]
return a + 1
盛最多水的容器
問題來源：
力扣：11. 盛水最多的容器
問題簡述：
給出了寬度（索引之差），以及高度（最小元素值），求出最大矩形面積，
問題分析：
我們可以設定頭尾指標，實時記錄最大的矩形面積，指標更新按照如下規則：
- 頭指標對應的值更小，則頭指標后退一位；
- 尾指標對應的值更小，則尾指標前進一位；
- 頭尾指標對應的值相同，則相向進一位，
代碼
class Solution:
def maxArea(self, height: List[int]) -> int:
a, b = 0, len(height)-1
res = 0
while a < b:
res = max(res, min(height[a], height[b])*(b-a))
if height[b] > height[a]:
a += 1
elif height[b] < height[a]:
b -= 1
else:
a += 1
b -= 1
return res
三數之和
問題來源：
力扣：15. 三數之和
問題簡述：
在一個整數陣列中找出三個元素，這三個元素的和為0，輸出所有滿足條件且不重復的組合，
問題分析：
相信很多人對這道題的第一反應就是三層回圈直接找出三個數并判斷其和是否等于0，但這樣做的時間復雜度為O(N^3)，
如何優化呢？我們可以將陣列排序，排序后會發現上一個方法中后兩層回圈可以通過雙指標合并成一個回圈：
外層回圈可以得到a的值，第二層回圈可以得到b的值，不難發現，在a已知的情況下，b和c的值呈線性關系，若b偏大c必定偏小，反之亦然，我們將c通過一個指標指向陣列尾部，在第二層回圈中可以判斷，若a+b+c>0，那么c對應的指標可以向前移動，因為可能成立的c值一定在左側，又因為陣列是升序排列，b的值只會不斷增大，因此c的值必定呈遞減趨勢，
代碼
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
# 列舉 a
for first in range(n):
# 需要和上一次列舉的數不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 對應的指標初始指向陣列的最右端
third = n - 1
target = -nums[first]
# 列舉 b
for second in range(first + 1, n):
# 需要和上一次列舉的數不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保證 b 的指標在 c 的指標的左側
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指標重合，隨著 b 后續的增加
# 就不會有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出回圈
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/165345.html
標籤：Python