最近参与了一些面试工作，于是想着从 LeetCode 上找一些备选的算法题目，用于测试面试者的算法能力，本着希望一个算法既能够让面试者可以通过通俗的方式解决，不至于太过打击其信心，又不至于太过简单或太过常见，无法判断出面试者对于算法问题的思考这种心态，发现了一个不错的题目，即使标题上已经说了的，Valid Triangle Number，这个题目可以认为是 Three Sum 的变种，却又不能完全套用 Three Sum 的解决方式去解，而且这个题目有三种解法，每种解法越来越来，效率也越来越高。

题目描述

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

  1. The length of the given array won’t exceed 1000.
  2. The integers in the given array are in the range of [0, 1000].

先说结论，这个题目的三种解法分别是：

  1. 第一种，直接通过三重循环做，最暴力也最容易想到
  2. 第二种，Three Sum 解法的变种，而且有三种变种，每一种解决方式又略有不同，值得深挖
  3. 第三种，根据题目条件而有的取巧解法，发现这种解法的人，不得不说是一个观察细致的人

分析

这个题目无非就是任意组合三个数字，是他们能够满足三角形的变长关系：

  1. a + b > c
  2. a + c > b
  3. b + c > a

三重循环

这样一组关系，所以最容易想到的就是直接三重循环暴力解题了。

public int triangleNumber(int[] nums) {
    if (nums.length < 3) {
        return 0;
    }
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i+1; j < nums.length; j++) {
            for (int k = j+1; k < nums.length; k++) {
                int a = nums[i];
                int b = nums[j];
                int c = nums[k];
                if (a + b > c) {
                    count++;
                }
            }
        }
    }
    return count;
}

这种方式想起来简单，写起来也简单，但是如果作为一个算法题来这么解肯定是不得分的，此处列出来只是为了与后面的解法进行对比。

定一变二

然后这道题目能够很轻松地联想到另一个很常见的题目，Three Sum，题目的内容就是在一个数组中，任务三个数求这三个数的和等于一个定值的组合数量，乍一看跟这道题几乎一摸一样，但是其实它们还是有差别的，在 Three Sum 中三数之和等于一个定值，也就是说所有的判断关系都是基于等于/不等于的，而在这个这道题中，判断关系是基于满足/不满足三角形的三边关系的，个人感觉是相对更难的，因为做这道题，首先得要知道三角形的三边关系是什么吧，然后才能基于判断结果进行解题。

解题要点

首先说一下关于三数之和问题的基本思路，首先数组需要是有序的，我们选定其中一个数字，比如 a，那么接下来的问题就是求满足 b + c = d 这样一个条件的 b 和 c 的值，那么就可以得到下面的结论：

  1. 当 b + c > d 时，要想达到满足的条件，需要使 b + c 值变小，即 b 减小，或 c 减小
  2. 当 b + c < d 时，想要达到满足的条件，需要使 b + c 值变大，即 b 增加，或 c 增加
  3. 当 b + c = d 时，已经达到了满足条件，那么接下来需要朝着 b + c 不变的方向尝试，即 b 增加，c 减小

然后我们再规定一下 b 和 c 的关系，有 b <= c，且 b 的初值取最小的，c 的初值取最大的，即 b 只能增加，c 只能减小，那么上述的条件就变成了：

  1. 当 b + c > d 时，要想达到满足的条件，需要使 b + c 值变小，即 c 减小
  2. 当 b + c < d 时，想要达到满足的条件，需要使 b + c 值变大，即 b 增加
  3. 当 b + c = d 时，已经达到了满足条件，那么接下来需要朝着 b + c 不变的方向尝试，即 b 增加 且 c 减小

如果我们将 b + c > d 和 b + c < d 都看作是一种中间状态，b + c = d 看作是目标状态，那么就是有两种中间状态，一种目标状态（其实在本题中 b + c = d 也可以看作是一种中间状态，它要向下一种目标状态移动），然后有两个变量 b 和 c，它们都有且只有一种移动趋势，然后我们就可以发现，恰好每一种中间状态都有且只有一种变量的移动趋势，使之能够向目标状态移动。

那么这样一来，我们就可以将这个二维问题通过一维方式来解决，即分别移动 b c，虽然它们都还在移动，但是他们在一起移动的次数却被限制在了一维的数量级内。

最后再总结一下这种将二维问题转化为一维问题解法的适用范围：

  1. 每一个变量有且只有一种趋势（比如 b 增加的趋势，c 减小的趋势），且趋势的范围有限
  2. 每一种中间状态要想向目标状态转化，都对应着唯一一种趋势

本题解法

接下来再看本题，大致的思路一致，我们可以先规定三边的关系，a <= b <= c，然后取个最小的 a 先做第一重遍历，那么剩下的就是变量 b c，它们的取值范围分别是：

  1. b [a+1, c-1]
  2. c [b+1, count-1]

目标状态（也就是 a b c 满足三角形三边）为 a + b > c（这里因为限制了 a <= b <= c，则必满足 a + c > b 和 b + c > a），那么中间状态就是 a + b <= c 了。假设就是选 a 作为第一重遍历，那么还剩下两个变量，b c，于是就有下面的推断：

  1. 当 a + b <= c 时，要想达到满足的条件，需要 b 增加或 c 减小
  2. 当 a + b > c 时，已达到满足条件，并能够得出结论：
    1. 若 b 可增加，则任意大于当前 b 的值都可以继续与 a c 构成三角形
    2. 若 c 可减小，则任意小于当前 c 的值都可以继续与 a b 构成三角形
    3. 若此时再向下一个满足条件移动，需要 b 减小或 c 增加

那么接下来就是确认 b c 的初值与移动趋势了，比如，先假设 b 的初值为 a+1，为增加趋势，c 的初值为 count-1，为减小趋势，这种情况下的话，就会导致当处于 a + b <= c 状态时，b 和 c 的趋势都符合它的要求，那么这显然是不行的，理想的状态应该是 b c 都有增加或减小的趋势，从而使 a + b <= c 往 a + b > c 移动时，对应的唯一一种趋势。

所以，当我们假设 b 初值为 a+1，有增加趋势时，c 也要是有增加趋势，而因为 c 的范围是 [b+1, count-1]，所以可以得出 c 的初值为 b+1，于是就可以得到下面的结论：

  1. 当 a + b <= c 时，要想达到满足的条件，需要 b 增加
  2. 当 a + b > c 时，已达到满足条件
    1. 任意大于当前 b 的值都可以继续与 a c 构成三角形
    2. 此时再向下一个可能的满足条件移动，需要 c 增加
b c 为可变量

这就是这道题的解了，用代码表达出来就是：

public int triangleNumber(int[] nums) {
    if (nums.length < 3) {
        return 0;
    }
    Arrays.sort(nums);
    int ret = 0;
    for (int aIndex = 0; aIndex < nums.length; aIndex++) {
        int bIndex = aIndex + 1;
        int cIndex = bIndex + 1;
        while (cIndex < nums.length) {
            if (bIndex >= cIndex) {
                cIndex++;
            }
            while (bIndex < cIndex && cIndex < nums.length) {
                int a = nums[aIndex];
                int b = nums[bIndex];
                int c = nums[cIndex];
                checkCount++;
                checkArray.add(Arrays.asList(a, b, c));
                if (a + b > c) {
                    ret += cIndex - bIndex;
                    cIndex++;
                    break;
                } else {
                    bIndex++;
                }
            }
        }
    }
    return ret;
}

类似的，也可以将 b 和 c 的初值分别设置为 c-1 和 count-1，且都是递减趋势，也可以得到类似的代码：

public int triangleNumber(int[] nums) {
    if (nums.length < 3) {
        return 0;
    }
    Arrays.sort(nums);
    int ret = 0;
    for (int aIndex = 0; aIndex < nums.length; aIndex++) {
        int bIndex = nums.length-2;
        int cIndex = nums.length-1;
        while (aIndex < bIndex) {
            if (bIndex >= cIndex) {
                bIndex--;
            }
            while (aIndex < bIndex && bIndex < cIndex) {
                int a = nums[aIndex];
                int b = nums[bIndex];
                int c = nums[cIndex];
                checkCount++;
                checkArray.add(Arrays.asList(a, b, c));
                if (a + b > c) {
                    ret += cIndex - bIndex;
                    bIndex--;
                    break;
                } else {
                    cIndex--;
                }
            }
        }
    }
    return ret;
}
a c 为可变量

再延伸出来，可以有先第一重遍历 b，可变量为 a c，那么 a 的范围是 [0, b-1]，c 的范围是 [b+1, count-1]，那么可以接着设置 a 的初值为 0，c 的初值为 b+1，都呈增加趋势，

public int triangleNumber(int[] nums) {
    if (nums.length < 3) {
        return 0;
    }
    Arrays.sort(nums);
    int ret = 0;
    for (int bIndex = 1; bIndex < nums.length; bIndex++) {
        int aIndex = 0;
        int cIndex = bIndex+1;
        while (aIndex < bIndex && cIndex < nums.length) {
            int a = nums[aIndex];
            int b = nums[bIndex];
            int c = nums[cIndex];
            checkCount++;
            checkArray.add(Arrays.asList(a, b, c));
            if (a + b > c) {
                ret += bIndex - aIndex;
                cIndex ++;
            } else {
                aIndex ++;
            }
        }
    }
    return ret;
}

也可以是都呈减少趋势，取 a 的初值为 b-1，c 的初值为 count-1。

a b 为可变量

或者可以继续选 c 作为第一重遍历，以 a b 为可变量，那么它们的范围就是 [0, b-1] 和 [a+1, c-1]，而这时候的条件就与上面两种情况不同了。因为目标状态是 a + b > c，如果以 a b 为可变量的话，它们就不能再以同样的趋势出现了，而必须是一个增加趋势，一个减少趋势，所以这就限定了，当以 a b 为可变量的时候，只能是 a 增加趋势，b 减少趋势，故而 a 的初值为 0，b 的初值为 c-1，相应的代码为：

public int triangleNumber(int[] nums) {
    if (nums.length < 3) {
        return 0;
    }
    Arrays.sort(nums);
    int count = 0;
    for (int cIndex = 2; cIndex < nums.length; cIndex++) {
        int aIndex = 0;
        int bIndex = cIndex-1;
        while (aIndex < bIndex) {
            int a = nums[aIndex];
            int b = nums[bIndex];
            int c = nums[cIndex];
            checkCount++;
            checkArray.add(Arrays.asList(a, b, c));
            if (a + b <= c) {
                aIndex += 1;
            } else {
                count += bIndex - aIndex;
                bIndex -= 1;
            }
        }
    }
    return count;
}
延伸

从以上的说明可以看出，就这个题而言，光是“定一变二”这种解法，就可以得到五种不同的答案，那么接下来，可不可以更细致地分析这五种解法之间的异同，它们中是否有效率上的差别？是什么导致效率上的差别的？是否对我们有更多的启发？这些就下次有时间再详细分析下。

取巧解法

最后还有一种相对来说比较取巧的解法，是一种以空间换时间的做法，当然相对的限制也更多。要想使用这种解法就需要关注到题目中给的条件，也就是数组的长度范围，和数组中的数字范围，都是 [0, 1000]，是一个很小的数字了，那我们就可以考虑到，这个题目是不是可以通过某种空间换时间的方式去做，比如先声明一个长度为 1000 的数组，把每一个数字的数量记录下来。那我们就可以得到下面的信息：

  1. 数字的范围
  2. 每一个数字的个数

上面的两种解法，都是针对于不知道每个数字的大小，所以需要遍历数组，每遇到一个新的数字之后，从条件来判断这个数字是否符合要求，而如果我们有了以上两个信息，那我们就可以反过来，通过需要满足的条件，反过来求需要的数字的个数，就可以得到最终满足三角形的条件的数字组合。

比如，当我们知道 a 和 b 的值之后，就可以直接根据 a + b > c 这个条件，求出来满足条件的 c 的范围是多少，然后就可以根据满足条件的 c 的范围，根据已经求出来的每一个数字的个数，求出来满足条件的 c 的个数，此时的 c 的个数，就是 a b 为定值的时候满足条件的个数。那么就可以直接将原本的三维问题转换成二维问题。

但是这里需要考虑，由于此处是直接遍历边长的，那么对于那种三边一样长，或者三边中有两条边一样长的组合，在这种解法中就需要单独考虑。具体的代码如下：

public int triangleNumber(int[] nums) {
    if (nums.length < 3) {
        return 0;
    }
    int ret = 0;
    int max = 0;
    int[] count = new int[1001];
    for (int n : nums) {
        count[n]++;
        max = Math.max(max, n);
    }
    int[] sum = new int[max+1];
    for (int i = 1; i < max+1; i++) {
        sum[i] = sum[i-1] + count[i];
    }
    for (int a = 1; a <= max; a++) {
        if (count[a] >= 3) {
            // Cn3
            ret += (count[a] * (count[a] - 1) * (count[a] - 2)) / 6;
        }
        for (int b = a+1; b <= max; b++) {
            if (count[b] == 0) continue;
            if (count[a] >= 2 && b < a * 2) {
                // Cn2 * Cn1
                ret += (count[a] * (count[a] - 1)) / 2 * count[b];
            }
            if (count[b] >= 2) {
                // Cn1 * Cn2
                ret += (count[b] * (count[b] - 1)) / 2 * count[a];
            }
            int c = Math.min(max, a+b-1);
            ret += count[a] * count[b] * (sum[c] - sum[b]);
        }
    }
    return ret;
}

在这里，有几点需要注意的：

  1. 为了兼容到三边中有相等边的存在，所以在遍历的时候，兼顾地考虑到了，如果 count[a] > 3，意味着任取三个 a 都可以组成一个三角形，所以是按照排列组合 Cn3 来求 n 个 a 可以组成的三角形的个数，同理，考虑到有两个 a 一个 b 或者一个 a 两个 b 的情况，也都是通过组合来求的
  2. 代码中还额外求了 sum 数组，表示从 0 到 i 的数字的总和，这就能够有效地降低求 c 的个数的过程，知道了 c 的范围是 b 到 c 之后，就可以通过 sum 快速求出可能的 c 的数量