有效三角形的个数

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

数据范围

数组长度不超过1000。
数组里整数的范围为 [0, 1000]。

示例

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:

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

思路一

双指针加贪心

先排序，固定一值k，利用双指针i,j，判断是否能构成三角形

判断三角形方法：

• 两边之和大于第三边，即nums[i] + nums[j] > nums[k]

同时，若有i,j 满足nums[i] + nums[j] > nums[k]，则同时有

• nums[i+1] + nums[j] > nums[k]
• nums[i+2] + nums[j] > nums[k]
• nums[i+3] + nums[j] > nums[k]
• …..
• nums[j-1] + nums[j] > nums[k]

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

AC代码一

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        if(nums.size() < 3) return 0;
        sort(nums.begin(),nums.end());
        int ans = 0;
        for(int k = nums.size() - 1;k >= 2;k--){
            int i = 0,j = k - 1;
            while(i < j){
                if(nums[i] + nums[j] > nums[k]){
                    ans += j - i;
                    j--;
                }else{
                    i++;
                }
            }
        }
        return ans;
    }
};

思路二

暴力美学
直接开三个循环，赌这个数据量能过

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

代码二

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        if(nums.size() < 3) return 0;
        int ans = 0,n = nums.size();
        sort(nums.begin(),nums.end());
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
                for(int k = j+1;k < n;k++){
                    if(nums[i] + nums[j] > nums[k])
                        ans++;
                }
            }
        }
        return ans;
    }
};

我试过了，超时，明明数据量也不大，真是。

思路三

排序加二分查找
先排序，在开个双重循环，充当两条较小边，使用二分查找，找到满足条件的最大的边。

AC代码

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int left = j + 1, right = n - 1, k = j;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] < nums[i] + nums[j]) {
                        k = mid;
                        left = mid + 1;
                    }
                    else {
                        right = mid - 1;
                    }
                }
                ans += k - j;
            }
        }
        return ans;
    }
};