611.有效三角形的个数

题目

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

过程

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


    }
};

不知道怎么用双指针做，只能穷举了。因为双指针的话，我应该前进哪一边呢？有三个指针，应该是先固定一端，后面往哪前进不知道了

解法

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

有点巧妙，res+=(k-j)。有的指针并不需要前进，因为可以直接算出规律。只有最小的和最大的加起来不大于最右边的值，才动最小值。如果大于最右边的值，最小的都大于了，那往后遍历都可以大于，把这些方案进行汇总，然后再去移动偏大值的指针。

原文地址：https://blog.csdn.net/qq_43920838/article/details/144145590

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！