README_EN.md

1395. Count Number of Teams

中文文档

Description

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] <= 105
• All the integers in rating are unique.

Solutions

Python3

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n, ans = len(rating), 0
        for j in range(1, n - 1):
            ia = ib = ka = kb = 0
            for i in range(j):
                if rating[i] < rating[j]:
                    ia += 1
                elif rating[i] > rating[j]:
                    ib += 1
            for k in range(j + 1, n):
                if rating[j] < rating[k]:
                    ka += 1
                elif rating[j] > rating[k]:
                    kb += 1
            ans += ia * ka + ib * kb
        return ans

Java

class Solution {
    public int numTeams(int[] rating) {
        int n = rating.length;
        int ans = 0;
        for (int j = 1; j < n - 1; ++j) {
            int ia = 0;
            int ib = 0;
            int ka = 0;
            int kb = 0;
            for (int i = 0; i < j; ++i) {
                if (rating[i] < rating[j]) {
                    ++ia;
                } else if (rating[i] > rating[j]) {
                    ++ib;
                }
            }
            for (int k = j + 1; k < n; ++k) {
                if (rating[j] < rating[k]) {
                    ++ka;
                } else if (rating[j] > rating[k]) {
                    ++kb;
                }
            }
            ans += ia * ka + ib * kb;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size(), ans = 0;
        for (int j = 1; j < n - 1; ++j)
        {
            int ia = 0, ib = 0, ka = 0, kb = 0;
            for (int i = 0; i < j; ++i)
            {
                if (rating[i] < rating[j]) ++ia;
                else if (rating[i] > rating[j]) ++ib;
            }
            for (int k = j + 1; k < n; ++k)
            {
                if (rating[j] < rating[k]) ++ka;
                else if (rating[j] > rating[k]) ++kb;
            }
            ans += ia * ka + ib * kb;
        }
        return ans;
    }
};

Go

func numTeams(rating []int) int {
	n, ans := len(rating), 0
	for j := 1; j < n-1; j++ {
		ia, ib, ka, kb := 0, 0, 0, 0
		for i := 0; i < j; i++ {
			if rating[i] < rating[j] {
				ia++
			} else if rating[i] > rating[j] {
				ib++
			}
		}
		for k := j + 1; k < n; k++ {
			if rating[j] < rating[k] {
				ka++
			} else if rating[j] > rating[k] {
				kb++
			}
		}
		ans += ia*ka + ib*kb
	}
	return ans
}

...