題目出處
難度
medium
個人範例程式碼 - two pointers
from typing import (
List,
)
class Solution:
"""
@param nums: an array of integer
@param target: An integer
@return: An integer
"""
def two_sum6(self, nums: List[int], target: int) -> int:
if not nums:
return 0
nums.sort()
ans = 0
start, end = 0, len(nums)-1
while(start < end):
if(start > 0 and nums[start] == nums[start - 1]):
start += 1
continue
if(end < len(nums)-1 and nums[end] == nums[end + 1]):
end -= 1
continue
if nums[start] + nums[end] == target:
ans += 1
start += 1
end -= 1
elif nums[start] + nums[end] < target:
start += 1
else: # nums[start] + nums[end] > target:
end -= 1
else:
return ans
算法說明
簡單的組合，先 sort 後以 two pointers 處理，
而注意重複，這邊以第一次就去做為準下去寫。
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理 input 為 [] 的情況，輸出 0。
Boundary conditions
結束條件
相向相交時，start < end
處理重複
這邊以第一次就去做為準下去寫。
因此有
if(start > 0 and nums[start] nums[start - 1]):
start += 1
continue
if(end < len(nums)-1 and nums[end] nums[end + 1]):
end -= 1
continue
特別注意「start > 0」、「end < len(nums)-1」這兩個部分。