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

1
2
3
4
5
6
7

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

方法一：排序 + 二分查找

思路：

对于正整数a，b，c，他们可以作为三角形的三条边，当且仅当任意两边之和大于第三边均成立。如果将三条边升序排列，使得a<=b<=c,那么只需要a+b>c成立即可。

将数组nums进行升序排列，然后使用二重循环枚举a和b。设a=nums[i],b=nums[j]，为了防止重复统计答案，需要保证i<j。剩余的边c需要满足c<num[i]+num[j],我们在[j+1,n-1]的下标范围内使用二分查找(其中n是数组nums的长度)，找出最大的满足nums[k]<nums[i]+nums[j]的下标k，那么在[j+1,k]范围内的下标都可以作为边c的下标，我们将范围的长度k-j累加答案。当枚举完成时，返回累加的答案即可

细节：

题目中描述nums包含的元素的非负整数，即除了正整数以外，nums还包含0。但如果将nums进行升序排序，那么在枚举a和b出现了0，那么nums[i]一定为0.此时，边c需要满足c<nums[i]+nums[j]=nums[j],而下标在[j+1,n-1]范围内的元素一定都是大于等于num[j]的，因此二分查找法会失败。若二分查找失败，令k=j，此时对应的范围长度k-j=0，保证了答案的正确性。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                left, right, k = j + 1, n - 1, j
                while left <= right:
                    mid = (left + right) // 2
                    if nums[mid] < nums[i] + nums[j]:#查找成功修改k
                        k = mid
                        left = mid + 1
                    else:#查找失败
                        right = mid - 1
                ans += k - j
        return ans

复杂度分析：

  • 时间复杂度：O(n^2 log n)，其中 n 是数组 nums 的长度。我们需要 O(nlogn) 的时间对数组 nums 进行排序，随后需要 O(n^2 log n)的时间使用二重循环枚举 a, b 的下标以及使用二分查找得到 c 的下标范围。

  • 空间复杂度：O(logn)，即为排序需要的栈空间。

方法二：排序 + 双指针

思路：

将a=num[i],b=num[j]时，最大满足nums[k]<nums[i]+nums[j]的下标k记为k_i,j。如果我们固定i，那么随着j的递增，不等式右侧nums[i]+nums[j]也是递增的，因此k_i,j也是递增的。这样，我们就可以将j和k看成两个同向(递增)移动的指针。

  • 使用一重循环枚举i。当i固定时，使用双指针同时维护j和k，初始值均为i
  • 每一次将j向右移动一个位置，即j=j+1，并尝试不断向右移动k，使得k是最大的满足nums[k]<nums[i]+nums[j]的下标。将max(k-j,0)累加入答案。

细节：

与方法一中「二分查找的失败」类似，方法二的双指针中，也会出现不存在满足 nums[k]<nums[i]+nums[j]的下标的情况。此时，指针 k 不会出现在指针 j 的右侧，即 k - j ≤0，因此我们需要将 k - j 与 0 中的较大值累加入答案，防止错误的负数出现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        ans = 0
        for i in range(n):
            k = i
            for j in range(i + 1, n):
                while k + 1 < n and nums[k + 1] < nums[i] + nums[j]:
                    k += 1
                ans += max(k - j, 0)
        return ans

复杂度分析：

  • 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。我们需要 O(nlogn) 的时间对数组 nums 进行排序，随后需要 O(n^2)的时间使用一重循环枚举 a 的下标以及使用双指针维护 b,c 的下标。

  • 空间复杂度：O(logn)，即为排序需要的栈空间。

二分查找法：

（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。

（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。

（3）如果某一步数组为空，则表示找不到目标元素。

二分法查找的时间复杂度O(logn)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

function binarySearch(arr,key){
	var low=0; //数组最小索引值
	var high=arr.length-1; //数组最大索引值
	while(low<=high){
		var mid=Math.floor((low+high)/2);
		if(key==arr[mid]){
			return mid;
		}else if(key>arr[mid]){
			low=mid+1;
		}else{
			high=mid-1;
		}
	}
	return -1; //low>high的情况，这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
}

https://blog.csdn.net/u012194956/article/details/79103843