題目出處

• Amazon | OA 2019 | Two Sum – Unique Pairs
• 587 · Two Sum – Unique pairs

難度

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」這兩個部分。

Reference

• 两数之和 – 不同组成 · Two Sum – Unique pairs