Triangle Count 382

Question

Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?

Example

Given array S = [3,4,6,7], return 3. They are:

[3,4,6]

[3,6,7]

[4,6,7]

Given array S = [4,4,4,4], return 4. They are:

[4(1),4(2),4(3)]

[4(1),4(2),4(4)]

[4(1),4(3),4(4)]

[4(2),4(3),4(4)]

Solution

idea：想法与two sumII一样。target设为当前数组最大值，寻找之前元素中两个元素之和大于target的对数，然后再将target元素左移，寻找下一个target。

1. 对数组从小到大排序

2. 将元素最大值设为target，寻找之前元素中两个元素之和大于target的对数并计入总数

3. 将targte元素左移一位，重复2直到targte位置为2

4. 返回总数即为结果

代码如下：

public class Solution {
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int S[]) {
        // write your code here
        if(S == null || S.length <= 2){
            return 0;
        }

        Arrays.sort(S);

        int sum = 0;
        for(int i = S.length - 1; i >= 2; i--){
            int target = S[i];
            int left = 0;
            int right = i - 1;
            while(left < right){
                if(S[left] + S[right] > target){
                    sum += right - left;
                    right--;
                }else{
                    left++;
                }
            }
        }

        return sum;
    }
}