lintcode382. 三角形计数

ゝ一纸荒年。 2023-07-06 04:56 8阅读 0赞

给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？

样例
    样例 1:
    
    输入: [3, 4, 6, 7]
    输出: 3
    解释:
    可以组成的是 (3, 4, 6), 
               (3, 6, 7),
               (4, 6, 7)
    样例 2:
    
    输入: [4, 4, 4, 4]
    输出: 4
    解释:
    任何三个数都可以构成三角形
    所以答案为 C(3, 4) = 4

暴力破解：三层循环

class Solution {
        
    public:
        /**
         * @param S: A list of integers
         * @return: An integer
         */
        int triangleCount(vector<int> &S) {
        
            // write your code here
            sort(S.begin(),S.end());
            int res=0;
            for (int i = 0; i < S.size(); i++) {
        
                /* code */
                for(int j = i+1; j<S.size(); j++)
                {
        
                    int sum=S[i]+S[j];
                    for(int k = j+1; k<S.size()&&sum>S[k];k++) res++;
                }
            }
            return res;
        }
    };

利用左右两个指针来做：先进行从小到大排序  
3，4，6，7中，我们可以发现，3+6>7,则意味着往后的4+6>7必然成立，所以我们只需要找出一个最长边，然后位置较小的一个最短边，还有一个位置较大的最短边，两短边之和大于长边，则意味着较大位置到较小位置的这一段中都是满足三角形条件的

class Solution {
        
    public:
        /**
         * @param S: A list of integers
         * @return: An integer
         */
        int triangleCount(vector<int> &S) {
        
            // write your code here
            sort(S.begin(),S.end());
            int res=0;
            for (int i = 2; i < S.size(); i++) {
        
                /* code */
                int m=0;
                int n=i-1;
                while(m<n)
                {
        
                    if(S[m]+S[n]>S[i]){
        
                        res+=n-m;
                        n--;
                    } 
                    else m++;
                }
            }
            return res;
        }
    };