统计作战单位数

题目：

n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。
每 3 个士兵可以组成一个作战单位，分组规则如下：
从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n
请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。

示例：

输入：rating = [2,5,3,4,1]
输出：3
解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。

解题方法：

遍历[1，n-1]的士兵，对于第i个士兵，我们把他当做要选择作战单位的中间士兵，然后只需要统计在这个士兵左边/右边，大于/小于该士兵i评分rating。下面详细说明一下为什么这么做：

• 首先统计第i个士兵大于左边士兵rating的数量，记做lb；再记录小于右边的数量rs；现在满足条件的排列数为lb*rs（组合）
• 然后统计第i个士兵小于左边士兵rating的数量，记做ls；再记录大于右边的数量rb；现在满足条件的排列数为ls*rb（组合）
• 遍历完[1，n-1]的士兵，将所有统计的可能组合累加，得到最终结果。

为什么这样统计出来的没有重复呢？仔细想想，关键在于选择中间人作为筛选的条件，当筛选第i个士兵的时候，所有的组合都是i为中间人，但是当筛选第i+k个人的时候，i不可能在中间，所以这种遍历方式保证了不会出现重复的排列。

代码和结果：

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int nums=rating.size();
        int cnt=0;
        for(int i=1;i<nums-1;i++)
        {
            int lb=0;
            int ls=0;
            int rb=0;
            int rs=0;
            
            for(int j=0;j<i;j++)
            {
                if(rating[j]>rating[i])
                    lb++;
                else if(rating[j]<rating[i])
                    ls++;
            }

            for(int j=i+1;j<nums;j++)
            {
                if(rating[j]>rating[i])
                    rs++;
                else if(rating[j]<rating[i])
                    rb++;
            }
            cnt+=lb*rb+ls*rs;
        }
        return cnt;
    }
};

运行结果:

第200道题了，加油！

原题链接：https://leetcode-cn.com/problems/count-number-of-teams/