新乡定制网站建设公司,网络培训机构排名,凡克,网站大全官网1.题目解析 给定一个包含非负整数的数组 nums #xff0c;返回其中可以组成三角形三条边的三元组个数。 补充#xff1a;
1.三角形的判断#xff1a;假设有三条边按大小排序#xff1a; 2.题目示例 示例 1: 输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用…1.题目解析 给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。 补充
1.三角形的判断假设有三条边按大小排序 2.题目示例 示例 1: 输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3示例 2: 输入: nums [4,2,3,4]
输出: 4 分析题目可知是要算上重复的 3.算法分析
①暴力枚举
时间复杂度较高O(3*n^3)
三层for循环确定三条边再定义一个计数器计算有小三角形的个数
//暴力枚举public int triangleNumber(int[] nums) {Arrays.sort(nums);int count0;int lennums.length;for(int i0;ilen;i){for(int ji1;jlen;j){for(int kj1;klen;k){if(nums[i]nums[j]nums[k]){count;}}}}return count;}
集美们不用跑了我帮你们试过了过不了
解法二
利用单调性和双指针的方法
举个例子
22345678910
1.设置一个最大值
2.在最大数的左区间内使用双指针和单调性的方法计算出有效三角形的个数 本宝宝建议你自己画一画真正理解这个算法。 会出现两种情况 ①leftrightmax countright-left right-- ②leftrightmax lrft 代码实现 public int triangleNumber(int[] nums) {int lennums.length;int count0;for(int ilen-1;i0;i--){int maxnums[i];int left0;int righti-1;while (leftright){if(nums[left]nums[right]max){countright-left;right--;}else{left;}}}return count;}
当然这个代码你是跑不过的为什么呢
因为你无法确定最大值我举的栗子正好是我排过序的若是没有排过序不仅找不到最大值还无用大学生的方法判断是否是有效三角形所以一定要先排序(这都是姐走过的弯路) public int triangleNumber(int[] nums) {Arrays.sort(nums);int lennums.length;int count0;for(int ilen-1;i0;i--){int maxnums[i];int left0;int righti-1;while (leftright){if(nums[left]nums[right]max){countright-left;right--;}else{left;}}}return count;} 本题完欢迎指正
