สมมติว่าเรามีอาร์เรย์ที่ประกอบด้วยจำนวนเต็มที่ไม่เป็นลบ ภารกิจของเราคือนับจำนวน triplets ที่เลือกจากอาร์เรย์ที่สามารถสร้างสามเหลี่ยมได้หากเรานำมาเป็นความยาวด้านของสามเหลี่ยม ดังนั้นหากอินพุตเป็น [2,2,3,4] ผลลัพธ์จะเป็น 3 เป็น [2,3,4] โดยใช้ 2 ตัวแรก [2,3,4] ใช้ 2 อันที่สอง และ [2,2 ,3.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ret :=0, n :=ขนาดของ nums, sort nums
- สำหรับ i ในช่วง n – 1 เหลือ 0
- ขวา :=ผม – 1, ซ้าย :=0
- ขณะซ้าย <ขวา
- sum :=nums[left] + nums[right]
- ถ้าผลรวม> nums[i] ให้เพิ่ม ret โดยขวา – ซ้าย ลดทางขวา 1 มิฉะนั้น เพิ่มทางซ้าย 1
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int ret = 0;
int n = nums.size();
sort(nums.begin(), nums.end());
for(int i = n - 1; i >= 0; i--){
int right = i - 1;
int left = 0;
while(left < right){
int sum = nums[left] + nums[right];
if(sum > nums[i]){
ret += right - left;
right--;
}else left++;
}
}
return ret;
}
};
main(){
vector<int> v = {2,2,3,4};
Solution ob;
cout << (ob.triangleNumber(v));
} อินพุต
[2,2,3,4]
ผลลัพธ์
3
