Leetcode 1395. Count Number of Teams (python)

题目

暴力解法

class Solution {
    
public:int numTeams(vector<int>& rating) {
    int n = rating.size();int ans = 0;for (int i=0;i<n;i++){
    for (int j=i+1;j<n;j++){
    for (int k=j+1;k<n;k++){
    if ((rating[i]>rating[j] && rating[j]>rating[k]) || (rating[i]<rating[j] && rating[j]<rating[k])) {
    ans += 1;}}}}return ans;}};

改进解法

对于这种triplet的题目，一般可以优先考虑中间的元素。对于这道题，在固定中间元素的情况下，往两边找更大或者更小的元素。因为两边寻找的时候是相互独立的，所以可以将嵌套的循环变成平行的循环从而减少时间复杂度

class Solution:def numTeams(self, rating: List[int]) -> int:ans = 0for i in range(1,len(rating)):left_small = right_large = 0left_large = right_small = 0for j in range(0,i):if rating[j] < rating[i]:left_small += 1else:left_large += 1for k in range(i+1,len(rating)):if rating[k] > rating[i]:right_large += 1else:right_small += 1ans += left_small * right_largeans += left_large * right_smallreturn ans