leetcode算法练习【611】有效三角形的个数

男娘i 2023-02-11 15:29 82阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：三指针
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
    
    示例 1:
    
    输入: [2,2,3,4]
    输出: 3
    解释:
    有效的组合是: 
    2,3,4 (使用第一个 2)
    2,3,4 (使用第二个 2)
    2,2,3
    注意:
    
    数组长度不超过1000。
    数组里整数的范围为 [0, 1000]。

#### 方案：三指针 ####

class Solution { 
            public int triangleNumber(int[] nums) { 
                int len = nums.length;
                if (len < 3)
                    return 0;
                Arrays.sort(nums);
                int num = 0;
    
                int itimes = 0;
                int jtimes = 0;
                int tim_jtimes = 0;
    
                for (int i = 0; i < len - 2; i++) { 
                    if (nums[i] == 0)
                        continue;
                    else { 
                        for (int j = i + 1; j < len - 1; j++) { 
                            if (nums[j] == 0)
                                continue;
                            if (j > i + 1 && nums[j] == nums[j - 1]) { 
                                tim_jtimes = jtimes;
                                num += --jtimes;
                            } else { 
                                jtimes = 0;
                                for (int k = j + 1; k < len; k++) { 
                                    if (isTri(nums[i], nums[j], nums[k])) { 
                                        jtimes++;
                                        num++;
                                    } else
                                        continue;
                                }
                            }
                        }
                    }
                }
                return num;
            }
            public boolean isTri(int b1, int b2, int b3) { 
                return (b1 + b2 <= b3 || b2 + b3 <= b1 || b1 + b3 <= b2) ? false : true;
            }
    
        }

##### 复杂度计算 #####

*  时间复杂度：O(n 2)，去了个重，还可以，i的去重有点麻烦，没做
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode