There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

    You have to form a team of 3 soldiers amongst them under the following rules:

    • Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
    • A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

    Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

    Example 1:

    1. Input: rating = [2,5,3,4,1]
    2. Output: 3
    3. Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

    Example 2:

    1. Input: rating = [2,1,3]
    2. Output: 0
    3. Explanation: We can't form any team given the conditions.

    Example 3:

    1. Input: rating = [1,2,3,4]
    2. Output: 4

    Constraints:

    • n == rating.length
    • 1 <= n <= 200
    • 1 <= rating[i] <= 10^5

    题意

    从数组中选出三个下标i、j、k，使得rating[i]rating[j]>rating[k]。

    思路

    遍历数组(除头尾)，统计左/右边比当前元素小/大的数的个数，相乘求和即可得到以该元素作为中间数得到的组合的个数。

    代码实现

    1. class Solution {
    2.     public int numTeams(int[] rating) {
    3.         int ans = 0;
    5.         for (int i = 1; i < rating.length - 1; i++) {
    6.             int[] smaller = new int[2];
    7.             int[] larger = new int[2];
    9.             for (int j = 0; j < rating.length; j++) {
    10.                 if (rating[j] < rating[i]) {
    11.                     smaller[j < i ? 0 : 1]++;
    12.                 } else if (rating[j] > rating[i]) {
    13.                     larger[j < i ? 0 : 1]++;
    14.                 }
    15.             }
    17.             ans += smaller[0] * larger[1] + smaller[1] * larger[0];
    18.         }
    20.         return ans;
    21.     }
    22. }