[LintCode] 382 Triangle Count 解题报告

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

思路
三角形两边之和大于第三边。所以对于每一个S[i]，有多少对小于他数字的和大于S[i]？
上面这个问题其实就是Two Sum - Greater than target这题。
我们先把数组排序，然后遍历，并用双指针对每一个遍历到的数字求满足条件的对子数。全部加起来就是答案。



Code

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