LeetCode 题解工作台
找出给定方程的正整数解
给你一个函数 f(x, y) 和一个目标结果 z ，函数公式未知，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y 。满足条件的结果数对可以按任意顺序返回。 尽管函数的具体式子未知，但它是单调递增函数，也就是说： f(x, y) f(x, y) 函数接口定义如下： inter…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
根据题目我们可以知道，函数 $f(x, y)$ 是单调递增函数，因此，我们可以枚举 ，然后在 中二分查找 ，使得 $f(x, y) = z$。如果找到了，就将 $(x, y)$ 加入答案中。 时间复杂度 $(n \log n)$，其中 是 的值，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个函数 f(x, y) 和一个目标结果 z，函数公式未知，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。
尽管函数的具体式子未知，但它是单调递增函数，也就是说：
f(x, y) < f(x + 1, y)f(x, y) < f(x, y + 1)
函数接口定义如下：
interface CustomFunction {
public:
// Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
int f(int x, int y);
};
你的解决方案将按如下规则进行评判：
- 判题程序有一个由
CustomFunction的9种实现组成的列表，以及一种为特定的z生成所有有效数对的答案的方法。 - 判题程序接受两个输入：
function_id（决定使用哪种实现测试你的代码）以及目标结果z。 - 判题程序将会调用你实现的
findSolution并将你的结果与答案进行比较。 - 如果你的结果与答案相符，那么解决方案将被视作正确答案，即
Accepted。
示例 1：
输入：function_id = 1, z = 5 输出：[[1,4],[2,3],[3,2],[4,1]] 解释：function_id = 1 暗含的函数式子为 f(x, y) = x + y 以下 x 和 y 满足 f(x, y) 等于 5： x=1, y=4 -> f(1, 4) = 1 + 4 = 5 x=2, y=3 -> f(2, 3) = 2 + 3 = 5 x=3, y=2 -> f(3, 2) = 3 + 2 = 5 x=4, y=1 -> f(4, 1) = 4 + 1 = 5
示例 2：
输入：function_id = 2, z = 5 输出：[[1,5],[5,1]] 解释：function_id = 2 暗含的函数式子为 f(x, y) = x * y 以下 x 和 y 满足 f(x, y) 等于 5： x=1, y=5 -> f(1, 5) = 1 * 5 = 5 x=5, y=1 -> f(5, 1) = 5 * 1 = 5
提示：
1 <= function_id <= 91 <= z <= 100- 题目保证
f(x, y) == z的解处于1 <= x, y <= 1000的范围内。 - 在
1 <= x, y <= 1000的前提下，题目保证f(x, y)是一个 32 位有符号整数。
解题思路
方法一：枚举 + 二分查找
根据题目我们可以知道，函数 是单调递增函数，因此，我们可以枚举 ，然后在 中二分查找 ，使得 。如果找到了，就将 加入答案中。
时间复杂度 ，其中 是 的值，空间复杂度 。
"""
This is the custom function interface.
You should not implement it, or speculate about its implementation
class CustomFunction:
# Returns f(x, y) for any given positive integers x and y.
# Note that f(x, y) is increasing with respect to both x and y.
# i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
def f(self, x, y):
"""
class Solution:
def findSolution(self, customfunction: "CustomFunction", z: int) -> List[List[int]]:
ans = []
for x in range(1, z + 1):
y = 1 + bisect_left(
range(1, z + 1), z, key=lambda y: customfunction.f(x, y)
)
if customfunction.f(x, y) == z:
ans.append([x, y])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(n log n) using binary search per x to O(n) with a two-pointer approach, where n = 1000. Space complexity is O(1) aside from storing the result pairs. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you considering how the monotonic property can eliminate unnecessary checks?
- question_mark
Can you optimize function calls instead of brute forcing all pairs?
- question_mark
How will you ensure that all valid pairs are returned without duplicates?
常见陷阱
外企场景- error
Brute forcing all 1,000,000 x-y pairs without leveraging monotonicity.
- error
Assuming the function can be directly inverted without checking integer constraints.
- error
Failing to handle edge cases where x or y equals 1 or 1000.
进阶变体
外企场景- arrow_right_alt
Find pairs for a non-monotonic hidden function requiring full enumeration.
- arrow_right_alt
Return solutions where f(x, y) is within a tolerance range instead of exact z.
- arrow_right_alt
Optimize for very large ranges, e.g., 1 <= x, y <= 10^6, using modified search strategies.