สมมุติว่าเรามีอาร์เรย์ของตัวเลข เราต้องหาจำนวน triplets ที่เลือกจากอาร์เรย์ที่สามารถสร้างสามเหลี่ยมได้ ถ้าเราหามันเป็นความยาวด้านของสามเหลี่ยม ดังนั้นหากอินพุตเป็น [2,2,3,4] ผลลัพธ์จะเป็น 3 เนื่องจากมีแฝดสาม [2,3,4] ใช้ 2 ตัวแรก [2,3,4] ใช้ 2 อันที่สอง และ [2,2,3].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=0, n :=ขนาดของ nums, sort nums
-
สำหรับฉันอยู่ในช่วง n − 1 ลงไปที่ 0
-
ขวา :=i − 1, ซ้าย :=0
-
ขณะที่ซ้าย <ขวา
-
ผลรวม :=nums[ซ้าย] + nums[ขวา]
-
ถ้า sum> nums[i] ให้เพิ่ม ret โดย right − left, ลด right 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
