611. Valid Triangle Number三角形计数

［抄题］：

给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？

[暴力解法]：

全部都用for循环

时间分析：

空间分析：

［思维问题］：

可以用两层循环：for循环中嵌套while，用过但是没意识

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

用线段减法可以避免扫描多余状态
数组要先排序，提前注释中形成习惯

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

弄丢了left < right的前提，没有注意指针变化时要留边界

［总结］：

用线段减法避免扫描多余状态

［复杂度］：Time complexity: O(n^2) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

数组排序

［关键模板化代码］：

for (int i = 0; i < S.length; i++) {
            int left = 0;
            int right = i - 1;
            while (left < right) {

for中嵌套while

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

public class Solution {
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleNumber(int[] nums) {
        //corner case
        int result = 0;
        //sort first!!
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                result += right - left;
                right--;
                }else {
                left++;
                }
            }
        }
        return result;
    }
}

View Code