LeetCode找方程正整数解：双重循环超时，单循环+while为何通过？

我在解决LeetCode题目《Find Positive Integer Solution for a Given Equation》时，写出了一段双重循环代码，但提交后超时；另一种单for循环结合while循环的解法却能正常通过。两种写法逻辑看似一致，想请教为何我的代码会超时？

我的超时代码： #

res = []
for x in range(1,1001):
    for y in range(1000,0,-1):
        test = customfunction.f(x,y)
        if test == z:
            res.append([x,y])
return res

通过的解法： #

def findSolution(self, customfunction, z):
    res = []
    y = 1000
    for x in range(1, 1001):
        while y > 1 and customfunction.f(x, y) > z:
            y -= 1
        if customfunction.f(x, y) == z:
            res.append([x, y])
    return res

核心原因：利用函数单调性大幅减少调用次数 #

这道题的关键隐藏条件是**customfunction.f(x,y)是关于x和y的单调递增函数**——当x固定时，y越大，f(x,y)的值越大；当y固定时，x越大，f(x,y)的值也越大。

你的双重循环完全没利用这个特性：每个x都从y=1000遍历到1，最坏情况下要调用f函数1000*1000=100万次，这很容易触发时间限制。

而通过的解法充分利用了单调性：

• 初始时y从1000开始，随着x递增（x从1到1000），满足f(x,y)=z的y值只会变小或不变（因为x变大后，要让f(x,y)等于z，y不能比之前更大）。
• 所以y只需要从当前位置往下调整，不需要每次都从1000重新遍历。整个过程中，f函数的调用次数最多是1000（x的循环次数）+1000（y最多从1000减到1的次数）=2000次，远小于100万次，自然不会超时。

内容的提问来源于stack exchange，提问作者DrNogNog