Triangle Count

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? 

Have you met this question in a real interview? 

Yes

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)]

两边之和大于第三边，是使用两个较小的边与最大的一条边进行比较


java

public class Solution {
    /*
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int[] nums) {
        // write your code here
        if (nums == null || nums.length < 3) {
            return -1;
        }
        int count = 0;
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; i--) {
            count += twoSum(nums, i - 1, nums[i]);
        }
        return count;
    }
    private int twoSum(int[] nums, int end, int target) {
        int left = 0, right = end, sum = 0, count = 0;
        while (left < right) {
            sum = nums[left] + nums[right];
            if (sum <= target) {
                left++;
            } else {
                count += (right - left);
                right--;
            }
        }
        return count;
    }
}