問題 アドレス
説明
非負整数の配列が与えられたとき、三角形の3辺を形成する三角形の数を数える
例1:
: [2,2,3,4]
: 3
:
効率的な組み合わせは:
2,3,4 (最初の2)を使う
2,3,4 (2)を使用する
2,2,3
注意:
配列の長さは1000を超えない。
配列中の整数の範囲は [0, 1000]。
事前知識
- ソート
- ダブルポインタ
- (毛沢東主義)を2つに分けます。
- 三角形の辺の関係
ブルートフォース法
アイデア
3つのセグメントのうち、どれか2つの和が3番目の辺より大きければ、3つのセグメントは三角形を形成できるこれは数学的な前提から始まります。つまり、3つの線分a、b、cが与えられたとき、線分a、b、cが三角形を形成できるのは、a＋b＞c、a＋c＞b、b＋c＞aを満たす場合であり、そうでない場合は三角形を形成できません。
パワーバックルには、数学的な前提知識を必要とするトピックがいくつかありますが、それは比較的簡単なもので、通常は高校数学程度の知識で、特に複雑なものではありません。通常は小中学校の知識で十分です。
" "
キーポイント分析
- 三角形の辺の関係
- トリプルループは3つの線分を識別します。
コード
コードサポート: Python
class Solution:
def is_triangle(self, a, b, c):
if a == 0 or b == 0 or c == 0: return False
if a + b > c and a + c > b and b + c > a: return True
return False
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
if self.is_triangle(nums[i], nums[j], nums[k]): ans += 1
return ans
「複雑性解析
- 時間の複雑さ：
N は配列の長さ。
- 空間の複雑さ
最適化された暴力的方法
アイデア
暴力的手法の時間複雑度は 
よし、これで良し。辛口でいきますよ。 他のブロガーがあまり触れないようなものでなければなりません。その理由は、知らないか、話すにはあまりに平凡だと思うからでしょう。
- 先ほど私は、データのサイズに基づく解の複雑さの区間は
であることがわかりました。
であるはずがありません。
.
- 時間の複雑さを減らす主な方法は、space-for-timeとsort-for-timeです。時間並べ替えは、全体の複雑さが0.5より大きい場合にのみ適用されます。
全体の複雑さが
ここで、全体の時間の複雑さは 
- is_triangle 関数には有効でない判定があります。
def is_triangle(self, a, b, c):
if a == 0 or b == 0 or c == 0: return False
# a + c > b および + c > a は定数が成り立つので、無効な判断である
if a + b > c and a + c > b and b + c > a: return True
return False
- 従って、a + b > cを見つけることが目標となり、ループの第3レベルを早期に終了することができます。
for i in range(n - 2):
for j in range(i + 1, n - 1):
k = j + 1
while k < n and num[i] + nums[j] > nums[k]:
k += 1
ans += k - j - 1
- これも単なる分岐の削減であり、複雑さは変わりません。さらに観察すると、kは毎回j + 1から始める必要はないことがわかります。代わりに、見つけたkの値から始めればいいのです。理由は簡単で、nums[i] + nums[j] > nums[k]のとき、nums[i] + nums[j] > nums[k]を満たす次の新しいkの値を見つけたい場合、このkはソートのため見つけたkより大きくなければならないので、前のkの値は無効でスキップできるからです。
for i in range(n - 2):
k = i + 2
for j in range(i + 1, n - 1):
while k < n and nums[i] + nums[j] > nums[k]:
k += 1
ans += k - j - 1
Kはバックオフしないので、最も内側のループは合計で最大N回実行され、全体の時間複雑度は 
"この複雑さの分析は、モノトニック・スタックのようなもので、組み合わせて理解することができます。
"
キーポイント分析
- ソート
コード
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
nums.sort()
for i in range(n - 2):
if nums[i] == 0: continue
k = i + 2
for j in range(i + 1, n - 1):
while k < n and nums[i] + nums[j] > nums[k]:
k += 1
ans += k - j - 1
return ans
「複雑性解析
- 時間の複雑さ
- 空間の複雑さ：ソートアルゴリズムに依存
