Example 1:
Input: [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3
Note:
- The length of the given array won't exceed 1000.
- The integers in the given array are in the range of [0, 1000].
[Thoughts]
对于一个三角形,只要满足两边之和大于第三边即可。这题可采用双指针遍历。
首先把数组排序一遍,保证其有序。
其次,遍历数组,每一个数字都作为第三条边的选择,然后在前面的数字中通过双指针来决定第一条边和第二条边。对于任何一个可能的三角形,比如下例,3 + 7 > 9,那么如果第二条边(7)不变,所以第一条边(3)之后的数字都可以是解。
[Code]
1: int triangleNumber(vector<int>& nums) {
2: if(nums.size() < 3) return 0;
3:
4: sort(nums.begin(), nums.end());
5:
6: int count = 0;
7: for(int third_edge =2; third_edge < nums.size(); third_edge++) {
8: int first_edge = 0, second_edge = third_edge-1;
9: while(first_edge < second_edge) {
10: if(nums[first_edge] + nums[second_edge] > nums[third_edge]) {
11: count+= second_edge - first_edge;
12: second_edge --;
13: }else {
14: first_edge ++;
15: }
16: }
17: }
18: return count;
19: }
No comments:
Post a Comment