本文共 1335 字，大约阅读时间需要 4 分钟。

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,2,3,4]

输出: 3

解释:

有效的组合是:

2,3,4 (使用第一个 2)

2,3,4 (使用第二个 2)

2,2,3

注意:

数组长度不超过1000。

数组里整数的范围为 [0, 1000]。

要注意的：边界的问题。

解题思路：第一种方式便是常见的遍历的方法了。

// 第一种方法	    public int triangleNumber(int[] nums) {
   	    	// 判断数组的长度	    	if(nums.length<3) {
   	    		return 0;	    	}	    	// 存储结果	    	int res = 0;	    	// 遍历	    	for(int i=0;i
   
    nums[k]&&nums[i]+nums[k]>nums[j]&&nums[j]+nums[k]>nums[i]) {
   	    					res++;	    				}	    			}	    		}	    	}	    	return res;	    }
   

时间复杂度为：O(N^3)

第二种方法 ：便是先对其排序，那么仅需遍历两边，然后找到满足第三边的那个最大值即可。而找这个最大值可通过二分查找的办法。找到最大值的左边界的值

// 第二种方法 确定前两个值之后，寻找第三个值用二分查找的办法 只需满足一条nums[i]+nums[j]>nums[k]	    public int triangleNumber_2(int[] nums) {
   	    	// 判断	    	if(nums.length<3) {
   	    		return 0;	    	}            Arrays.sort(nums);	    	// 结果存储	    	int res = 0;	    	for(int i=0;i
   
    >1);	    		if(nums[mid]>=target) {
   	    			right = mid-1;	    		}else {
   	    			left = mid+1;	    		}	    	}	    	return left;	    }
   

时间复杂度为：O(N^2*logN)

第三种解题思路：直接找

public int triangleNumber_3(int[] nums) {
   	    	if(nums.length<3) {
   	    		return 0;	    	}	    	// 排序	    	Arrays.sort(nums);	    	int res = 0;	    	for(int i=0;i
   
    nums[k]) {
   	    				k++;	    			}	    			res += k-j-1;	    		}	    	}	    	return res;	    }
   

时间复杂度为：O(N^2)

转载地址：https://codingchaozhang.blog.csdn.net/article/details/111937207 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！