三数固其一

介绍

所谓三数固其一,指的是我们在分析涉及到三个数的值/状态变化的时候,通过固定其中的一个数,从而能够更快更清晰的理清思路,找到解决方法的小技巧。如leetcode上的经典例题3Sum。单独列出这个小技巧是因为我面对这种题常常会陷入到多层循环而不可自拔…😂

例题

1395. Count Number of Teams

❓给定一个数组,让判断满足A[i] < A[j] < A[k]或者A[i] > A[j] > A[k],且i < j < k的组合一共有多少个。

💡题目看上去简单,好理解。正好最近对单调栈和动态规划有一定的心得,尝试做了下……最后还是没有逃脱无尽的debug深渊。。。

最后还是用的dfs做出来的,维护一个变量count,当count = 3时代表部分解满足了成为完全解的条件,返回1。这代码就不贴出来了,与本文主题无关。

回到三数固其一的思想,本题恰好就是有针对三个数的单调递增或者递减的区间求解。解答的关键在于我们需要固定变量j

以[10, 6, 7, 4, 9 ,5, 8]为例。我们假设j为7

于单调递增区间而言,该数组中能找到的长度为3的单调递增区间有[6, 7, 9], [6, 7, 8]。即1*2

于单调递减区间而言,区间为[10, 7, 4], [10, 7, 9], [10, 7, 5], [10, 7, 8]。即1*4

我们可以发现,对于单调递增区间,其个数为less[j] * greater[j],也就是j左边小于A[j]的个数乘以j右边大于A[j]的个数。同理推递减。

因此代码为:

def numTeams(self, rating: List[int]) -> int:
    n = len(rating)
    res = 0

    for i in range(1, n - 1):
        less = [0, 0]
        greater = [0, 0]
        for j in range(n):
            if rating[j] < rating[i]:
                if j < i:
                    less[0] += 1
                else:
                    less[1] += 1
            if rating[j] > rating[i]:
                if j < i:
                    greater[0] += 1
                else:
                    greater[1] += 1
        res += less[0]*greater[1] + greater[0]*less[1]
    return res

时间复杂度:O(n2),空间复杂度:O(1)。

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号