1395. Count Number of Teams

Medium

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:

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

Example 2:

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

Example 3:

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

Constraints:

• n == rating.length

• 3 <= n <= 1000

• 1 <= rating[i] <= 10^5

• All the integers in rating are unique.

解題

對每一個 index 統計其左邊小於它、左邊大於它、右邊小於它、右邊大於它的數量。

一個左邊小於+目前數字+一個右邊大於可以組成一個組合

一個右邊小於+目前數字+一個左邊大於可以組成一個組合

所以所有可能的組合就是 左邊小於*右邊大於 + 右邊小於*左邊大於

func numTeams(rating []int) int {
    res := 0

    for i:=0; i<len(rating); i++ {
        gl, sl, gr, sr := 0, 0, 0, 0 
        // 左邊大於目前index, 左邊小於目前index, 右邊大於目前index, 右邊小於目前index

        for j:=0; j<i; j++ {
            if rating[j] < rating[i] { sl++ }
            if rating[j] > rating[i] { gl++ }
        }

        for j:= i+1; j<len(rating); j++ {
            if rating[j] < rating[i] { sr++ }
            if rating[j] > rating[i] { gr++ }
        }

        res += gl*sr + sl*gr
    }

    return res
}