邳州网页设计_山东省建筑信息平台_关键词排名优化公司推荐_在线优化seo

链接：611. 有效三角形的个数 - 力扣（LeetCode）

算法原理：

数学知识：给三个数，判断是否能够构成三角形

优化：先对整个数组排序

方法一：暴力枚举

class Solution {public int triangleNumber(int[] nums) {int n = nums.length;Arrays.sort(nums);int ans = 0;for (int i = 0; i < n; i++) {for (int j = i - 1; j >= 0; j--) {for (int k = j - 1; k >= 0; k--) {if (nums[j] + nums[k] > nums[i]) ans++;}}}return ans;}
}

复杂度分析：

• 时间复杂度：排序时间复杂度为 O(nlogn)；三层遍历找所有三元祖的复杂度为 O(n^3)。整体复杂度为 O(n^3)
• 空间复杂度：O(logn)

方法二：利用单调性，使用双指针算法来解决问题 

1.先固定最大的数

2.在最大的数的左区间内，使用双指针算法，快速统计出符合要求的三元组的个数

class Solution {public int triangleNumber(int[] nums) {//1.优化，排序Arrays.sort(nums);//2.利用双指针解决问题int ret = 0, n = nums.length;for(int i = n - 1; i >= 2; i--){//先固定最大值//利用双指针快速统计出符合要求的三元组的个数int left = 0, right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;}
}