leetcode 611. Valid Triangle Number | 611. 有效三角形的个数（Java）

系统管理员 2023-01-24 02:12 16阅读 0赞

## 题目 ##

[https://leetcode.com/problems/valid-triangle-number/][https_leetcode.com_problems_valid-triangle-number]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

a, b, c 三指针，无剪枝优化，O(n^3)，居然通过了。  
思路是，用 a, c 固定首尾，让 b 在 a, c 之间从左至右游荡。

另外有 O(n^2) 的解法，详见：[官方题解][Link 1]，本文不再详述。

class Solution { 
        public int triangleNumber(int[] nums) { 
            Arrays.sort(nums);
            int a, b, c;
            int count = 0;
            for (a = 0; a < nums.length - 2; a++) { 
                for (c = a + 2; c < nums.length; c++) { 
                    for (b = a + 1; b < c; b++) { 
                        if (nums[a] + nums[b] > nums[c]) count++;
                    }
                }
            }
            return count;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_valid-triangle-number]: https://leetcode.com/problems/valid-triangle-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221004/7d53b9de913645eca603d3cfedcf672e.png
[Link 1]: https://leetcode.com/problems/valid-triangle-number/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221004/a19ece340c71486aa37df55c3347d33b.png