Triangle Count(三角形计数)

http://www.lintcode.com/zh-cn/problem/triangle-count/?rand=true

import java.util.Arrays;

public class Solution {


    /*
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int[] S) {
        // write your code here
        int res = 0;
        Arrays.sort(S);
        for (int i = 0; i < S.length - 2; i++) {
            for (int j = i + 1; j < S.length - 1; j++) {
                for (int k = j + 1; k < S.length; k++) {
//                    因为数组有序，所以只需要最长的小于其它两个的和，就满足任意两边的和大于第三边，
//                    短的两个的差肯定小于最长的，由上边的和的式子也能推导出其它两个差小于第三边
                    if (S[i] + S[j] > S[k]) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
}