有效三角形的个数（ LeetCode 611 ）
一、题目描述
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
- 数组长度不超过1000。
- 数组里整数的范围为 [0, 1000]。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效三角形的个数(611):https://leetcode-cn.com/problems/valid-triangle-number/
class Solution {
public int triangleNumber(int[] nums) {
// 先将数组排序
Arrays.sort(nums);
// 获取数组的长度
int n = nums.length;
// 统计可以组成三角形三条边的三元组个数，一开始为 0
int res = 0;
// 通过两个循环来定位三角形的两边
// 其中 nums[i] 为能形成三角形的三边中的最短边，因此 i 的范围为 [ 0 , n - 3 ]
for (int i = 0; i < n - 2; i++) {
// 其中 nums[j] 为能形成三角形的三边中的较短边，因此 j 的范围为 [ i + 1 , n - 2 ]
for (int j = i + 1; j < n - 1; j++) {
// nums 已经排好序，并且 i < j，因此 nums[i] < nums[j]
// 判断三条边能组成三角形的条件为：假设三条边长从小到大为 a < b < c ，当且仅当 a + b > c 这三条边能组成三角形。
// nums[i] 为 a，nums[j] 为 b，先计算出最短边和较短边之和
int sum = nums[i] + nums[j];
// 接下来，在 [ j + 1 , n - 1 ] 这个区间去寻找出最长边 c
// left 为当前区间最左侧的元素，可以获取到
int left = j + 1;
// right 为当前区间最右侧的元素，可以获取到
int right = n - 1;
// 在 while 循环里面，left 不断的 ++，而 right 不断的 --
// 当 [ left , right ] 这个区间不存在元素的时候，才跳出 while 循环，也就是当 left > right 时跳出循环
// 即当 left = right + 1 时，搜索区间没有元素了
// 由于 left 和 right 相遇的时候指向同一个元素，这个元素是存在于 [ left , right] 区间，这个区间就一个元素
// 所以此时 while 循环的判断可以使用等号
while (left <= right) {
// left + (right - left) / 2 和 (left + right) / 2 的结果相同
// 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大，导致相加的结果溢出的问题
// 比如数据 int 的最大值为 2,147,483,647
// 此时，left 为 2,147,483,640
// 此时，right 为 2,147,483,646
// 两者直接相加超过了 2,147,483,647，产生了溢出
int mid = left + (right - left) / 2;
// 两边之和大于中间元素的值，说明两边之和肯定大于 [ left , mid ] 这个区间中所有的元素
// 因此[ left , mid ] 这个区间中所有的元素都和 nums[i]、nums[j] 构成三角形
if (sum > nums[mid]) {
// 因此，缩小查找区间为 [ mid + 1 , right]
// 查看一下 [ mid + 1 , right] 是否也有元素可以和 nums[i]、nums[j] 构成三角形
left = mid + 1;
// 两边之和小于中间元素的值，说明两边之和肯定小于 [ mid , right ] 这个区间中所有的元素
// 因此 [ mid ，right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
}else if(sum < nums[mid] ) {
// 因此，缩小查找区间为 [ left , mid - 1]
// 此时，舍弃掉了 [ mid ，right]
right = mid - 1;
// 两边之和等于中间元素的值，和两边之和小于中间元素的值情况是一样的
// 说明两边之和肯定小于或者等于 [ mid , right ] 这个区间中所有的元素
// 因此 [ mid ，right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
}else if( sum == nums[mid] ){
// 因此，缩小查找区间为 [ left , mid - 1]
// 此时，舍弃掉了 [ mid ，right]
right = mid - 1;
}
}
// 来到这一步的时候，left = right + 1
// 如果此时两边之和大于了 right 指向的值 nums[right]
// 那么由于数组有序，并且 i < j < right
// 因此 nums[i] < nums[j] < nums[right]，也就是说 nums[i] 、nums[j] 、 nums[right] 可以构成三角形
// 并且 [ j + 1 , right ] 这个区间中所有的元素都可以和 nums[i] 、nums[j] 构成三角形
if (sum > nums[right] ) {
// 计算 [ j + 1 , right ] 这个区间中所有的元素
int ans = right - (j + 1) + 1;
// 这些元素都能和 nums[i] 、nums[j] 构成三角形，把结果累加上去
res += ans;
}
}
}
// 返回结果
return res;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效三角形的个数(611):https://leetcode-cn.com/problems/valid-triangle-number/
class Solution {
public:
int triangleNumber(vector<int>& nums) {
// 先将数组排序
sort(nums.begin(), nums.begin() + nums.size());
// 获取数组的长度
int n = nums.size();
// 统计可以组成三角形三条边的三元组个数，一开始为 0
int res = 0;
// 通过两个循环来定位三角形的两边
// 其中 nums[i] 为能形成三角形的三边中的最短边，因此 i 的范围为 [ 0 , n - 3 ]
for (int i = 0; i < n - 2; i++) {
// 其中 nums[j] 为能形成三角形的三边中的较短边，因此 j 的范围为 [ i + 1 , n - 2 ]
for (int j = i + 1; j < n - 1; j++) {
// nums 已经排好序，并且 i < j，因此 nums[i] < nums[j]
// 判断三条边能组成三角形的条件为：假设三条边长从小到大为 a < b < c ，当且仅当 a + b > c 这三条边能组成三角形。
// nums[i] 为 a，nums[j] 为 b，先计算出最短边和较短边之和
int sum = nums[i] + nums[j];
// 接下来，在 [ j + 1 , n - 1 ] 这个区间去寻找出最长边 c
// left 为当前区间最左侧的元素，可以获取到
int left = j + 1;
// right 为当前区间最右侧的元素，可以获取到
int right = n - 1;
// 在 while 循环里面，left 不断的 ++，而 right 不断的 --
// 当 [ left , right ] 这个区间不存在元素的时候，才跳出 while 循环，也就是当 left > right 时跳出循环
// 即当 left = right + 1 时，搜索区间没有元素了
// 由于 left 和 right 相遇的时候指向同一个元素，这个元素是存在于 [ left , right] 区间，这个区间就一个元素
// 所以此时 while 循环的判断可以使用等号
while (left <= right) {
// left + (right - left) / 2 和 (left + right) / 2 的结果相同
// 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大，导致相加的结果溢出的问题
// 比如数据 int 的最大值为 2,147,483,647
// 此时，left 为 2,147,483,640
// 此时，right 为 2,147,483,646
// 两者直接相加超过了 2,147,483,647，产生了溢出
int mid = left + (right - left) / 2;
// 两边之和大于中间元素的值，说明两边之和肯定大于 [ left , mid ] 这个区间中所有的元素
// 因此[ left , mid ] 这个区间中所有的元素都和 nums[i]、nums[j] 构成三角形
if (sum > nums[mid]) {
// 因此，缩小查找区间为 [ mid + 1 , right]
// 查看一下 [ mid + 1 , right] 是否也有元素可以和 nums[i]、nums[j] 构成三角形
left = mid + 1;
// 两边之和小于中间元素的值，说明两边之和肯定小于 [ mid , right ] 这个区间中所有的元素
// 因此 [ mid ，right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
}else if(sum < nums[mid] ) {
// 因此，缩小查找区间为 [ left , mid - 1]
// 此时，舍弃掉了 [ mid ，right]
right = mid - 1;
// 两边之和等于中间元素的值，和两边之和小于中间元素的值情况是一样的
// 说明两边之和肯定小于或者等于 [ mid , right ] 这个区间中所有的元素
// 因此 [ mid ，right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
}else if( sum == nums[mid] ){
// 因此，缩小查找区间为 [ left , mid - 1]
// 此时，舍弃掉了 [ mid ，right]
right = mid - 1;
}
}
// 来到这一步的时候，left = right + 1
// 如果此时两边之和大于了 right 指向的值 nums[right]
// 那么由于数组有序，并且 i < j < right
// 因此 nums[i] < nums[j] < nums[right]，也就是说 nums[i] 、nums[j] 、 nums[right] 可以构成三角形
// 并且 [ j + 1 , right ] 这个区间中所有的元素都可以和 nums[i] 、nums[j] 构成三角形
if (sum > nums[right] ) {
// 计算 [ j + 1 , right ] 这个区间中所有的元素
int ans = right - (j + 1) + 1;
// 这些元素都能和 nums[i] 、nums[j] 构成三角形，把结果累加上去
res += ans;
}
}
}
// 返回结果
return res;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 有效三角形的个数(611):https://leetcode-cn.com/problems/valid-triangle-number/
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
# 先将数组排序
nums.sort()
# 获取数组的长度
n = len(nums)
# 统计可以组成三角形三条边的三元组个数，一开始为 0
res = 0
# 通过两个循环来定位三角形的两边
# 其中 nums[i] 为能形成三角形的三边中的最短边，因此 i 的范围为 [ 0 , n - 3 ]
for i in range( 0 , n - 2 ):
# 其中 nums[j] 为能形成三角形的三边中的较短边，因此 j 的范围为 [ i + 1 , n - 2 ]
for j in range( i + 1 , n - 1 ):
# nums 已经排好序，并且 i < j，因此 nums[i] < nums[j]
# 判断三条边能组成三角形的条件为：假设三条边长从小到大为 a < b < c ，当且仅当 a + b > c 这三条边能组成三角形。
# nums[i] 为 a，nums[j] 为 b，先计算出最短边和较短边之和
sum = nums[i] + nums[j]
# 接下来，在 [ j + 1 , n - 1 ] 这个区间去寻找出最长边 c
# left 为当前区间最左侧的元素，可以获取到
left = j + 1
# right 为当前区间最右侧的元素，可以获取到
right = n - 1
# 在 while 循环里面，left 不断的 ++，而 right 不断的 --
# 当 [ left , right ] 这个区间不存在元素的时候，才跳出 while 循环，也就是当 left > right 时跳出循环
# 即当 left = right + 1 时，搜索区间没有元素了
# 由于 left 和 right 相遇的时候指向同一个元素，这个元素是存在于 [ left , right] 区间，这个区间就一个元素
# 所以此时 while 循环的判断可以使用等号
while left <= right :
# left + (right - left) / 2 和 (left + right) / 2 的结果相同
# 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大，导致相加的结果溢出的问题
# 比如数据 的最大值为 2,147,483,647
# 此时，left 为 2,147,483,640
# 此时，right 为 2,147,483,646
# 两者直接相加超过了 2,147,483,647，产生了溢出
mid = left + (right - left) // 2
# 两边之和大于中间元素的值，说明两边之和肯定大于 [ left , mid ] 这个区间中所有的元素
# 因此[ left , mid ] 这个区间中所有的元素都和 nums[i]、nums[j] 构成三角形
if sum > nums[mid] :
# 因此，缩小查找区间为 [ mid + 1 , right]
# 查看一下 [ mid + 1 , right] 是否也有元素可以和 nums[i]、nums[j] 构成三角形
left = mid + 1
# 两边之和小于中间元素的值，说明两边之和肯定小于 [ mid , right ] 这个区间中所有的元素
# 因此 [ mid ，right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
elif sum < nums[mid] :
# 因此，缩小查找区间为 [ left , mid - 1]
# 此时，舍弃掉了 [ mid ，right]
right = mid - 1
# 两边之和等于中间元素的值，和两边之和小于中间元素的值情况是一样的
# 说明两边之和肯定小于或者等于 [ mid , right ] 这个区间中所有的元素
# 因此 [ mid ，right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
elif sum == nums[mid] :
# 因此，缩小查找区间为 [ left , mid - 1]
# 此时，舍弃掉了 [ mid ，right]
right = mid - 1
# 来到这一步的时候，left = right + 1
# 如果此时两边之和大于了 right 指向的值 nums[right]
# 那么由于数组有序，并且 i < j < right
# 因此 nums[i] < nums[j] < nums[right]，也就是说 nums[i] 、nums[j] 、 nums[right] 可以构成三角形
# 并且 [ j + 1 , right ] 这个区间中所有的元素都可以和 nums[i] 、nums[j] 构成三角形
if sum > nums[right] :
# 计算 [ j + 1 , right ] 这个区间中所有的元素
ans = right - (j + 1) + 1
# 这些元素都能和 nums[i] 、nums[j] 构成三角形，把结果累加上去
res += ans
# 返回结果
return res
四、动画理解（没有声音）
隐藏内容
此处内容需要权限查看
