Sponsored
Sponsored
First, sort the array. Then, iterate through the array by selecting the third side of the triplet. Use a two-pointer technique to find valid pairs for the first and second sides. For each third side, initialize two pointers, one starting at the beginning of the list and the other just before the third side. Check the sum of the elements at the two pointers and compare it to the third side. If they form a valid triangle, move the inner pointer inward; otherwise, adjust the pointers accordingly.
Time Complexity: O(n^2), where n is the length of the input array because the main operations involve sorting and a nested loop.
Space Complexity: O(1) since it uses only a fixed amount of extra space.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int triangleNumber(vector<int>& nums) {
10 sort(nums.begin(), nums.end());
11 int count = 0;
12 for (int i = nums.size() - 1; i >= 2; --i) {
13 int left = 0, right = i - 1;
14 while (left < right) {
15 if (nums[left] + nums[right] > nums[i]) {
16 count += right - left;
17 --right;
18 } else {
19 ++left;
20 }
21 }
22 }
23 return count;
24 }
25};
26
27int main() {
28 vector<int> nums = {2, 2, 3, 4};
29 Solution sol;
30 cout << sol.triangleNumber(nums) << endl;
31 return 0;
32}This C++ implementation uses the standard library to sort the array and employs the same two-pointer method to count valid triangle triplets.
This approach involves checking every possible triplet from the array to see if they can form a triangle by comparing their sums directly. This solution is straightforward but less efficient since it considers all combinations without optimizations such as sorting or double pointers.
Time Complexity: O(n^3), as it checks every combination of three numbers in the array.
Space Complexity: O(1), requiring minimal additional storage.
1
public class Solution {
public int TriangleNumber(int[] nums) {
int count = 0;
for (int i = 0; i < nums.Length - 2; i++) {
for (int j = i + 1; j < nums.Length - 1; j++) {
for (int k = j + 1; k < nums.Length; k++) {
if (nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) {
count++;
}
}
}
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.TriangleNumber(new int[] {2, 2, 3, 4}));
}
}In C#, the brute force method involves three layers of nested loops to check if any set of three numbers can form a valid triangle based on the conditions described.