題目出處

382 · Triangle Count

難度

medium

個人範例程式碼

from typing import (
    List,
)

class Solution:
    """
    @param s: A list of integers
    @return: An integer
    """
    def triangle_count(self, s: List[int]) -> int:
        # write your code here
        if not s:
            return 0

        ans = 0 
        s.sort()

        for idx, max_edge in enumerate(s):
            # ans = self.count_triange_fix_max_edge(max_edge, ans, s, start=idx+1, end=len(s)-1)
            ans = self.count_triange_fix_max_edge(max_edge, ans, s, start=0, end=idx-1) # notice this !!!!!
        return ans

    def count_triange_fix_max_edge(self, max_edge, ans, s, start, end):
        while(start < end):
            if s[start] + s[end] > max_edge:
                ans += (end -start)
                end -= 1 # too big
            else: # if s[start] + s[end] <= max_edge:
                start += 1 # too small
        else:
            return ans

算法說明

3Sum 的延伸題，3Sum 可以視為 a + b = c 的問題，
此題為 a + b > c 的題型 (建議先解完 3Sum 再過來解此題。)

【Leetcode】python – [15] 3Sum 個人解法筆記 (updated: 2022/4/6)

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

處理 input 為 [] 的情況，輸出 0 。(題目沒說，但這邊先預留特殊狀況處理)

Boundary conditions

解這題要特別小心，很多細節要處理

1. 注意「最大邊」設定為哪一邊

我的策略是一開始就要決定好哪邊是最大邊，

2. 設定好「最大邊」後，討論結果的範圍

特別注意我們決定好「最大值」後，搜尋的範圍在 0 ~ 「idx-1」，

因此

# ans = self.count_triange_fix_max_edge(max_edge, ans, s, start=idx+1, end=len(s)-1) # wrong !!!
ans = self.count_triange_fix_max_edge(max_edge, ans, s, start=0, end=idx-1) # notice this !!!!!

3. 移動範圍

因為題目只要求「計數」，因此這邊我們相對不用處理到太細節，
而要使結果滿足 a + b > c 的情況有兩種可能，

• 我們先固定 c 後： 「a 增加」或「b 減少」

這裡有個加速的做法，因為我們知道當 a + b > c 的 b 已經滿足時，剩下的「b -> c」範圍等式必定成立，
因此我們可以直接「ans += (c-b)」，再來移動「結束位置」 (end -= 1)

而一般情況是，start += 1，來去滿足「還不夠大」的部分。

Reference

• 三角形计数 · Triangle Count