Medium

题目描述

给你一个可调用的函数 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:
  // 对于两个正整数 x 和 y，返回某个正整数 f(x, y)，基于隐藏的公式。
  int f(int x, int y);
};

示例 1：

输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,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]]
解释：隐藏的公式为 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 <= 9
  • 1 <= z <= 100
  • 保证 f(x, y) == z 的解在范围 1 <= x, y <= 1000 内
  • 保证当 1 <= x, y <= 1000 时，f(x, y) 能用 32 位有符号整数表示

解题思路

这道题利用了函数的单调递增性质，我们可以使用双指针技巧来高效求解。

核心思路： 由于 f(x, y) 对于 x 和 y 都是单调递增的，我们可以使用双指针从两个方向搜索：

  • 从 x = 1 开始，y = 1000 开始
  • 如果 f(x, y) < z，说明需要增大函数值，由于 y 已经很大，我们增加 x
  • 如果 f(x, y) > z，说明需要减小函数值，我们减少 y
  • 如果 f(x, y) == z，找到一个解，同时 x++ 和 y– 继续搜索

这种方法的时间复杂度是 O(1000) = O(1)，远优于暴力枚举的 O(1000²)。

其他解法：

  1. 暴力枚举：遍历所有可能的 (x,y) 组合，时间复杂度 O(n²)
  2. 二分查找：对于每个固定的 x，二分查找合适的 y，时间复杂度 O(n log n)

推荐解法： 双指针法，效率最高且代码简洁。

代码实现

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> result;
        int x = 1, y = 1000;
        
        while (x <= 1000 && y >= 1) {
            int val = customfunction.f(x, y);
            if (val == z) {
                result.push_back({x, y});
                x++;
                y--;
            } else if (val < z) {
                x++;
            } else {
                y--;
            }
        }
        
        return result;
    }
};

class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        result = []
        x, y = 1, 1000
        
        while x <= 1000 and y >= 1:
            val = customfunction.f(x, y)
            if val == z:
                result.append([x, y])
                x += 1
                y -= 1
            elif val < z:
                x += 1
            else:
                y -= 1
        
        return result

public class Solution {
    public IList<IList<int>> FindSolution(CustomFunction customfunction, int z) {
        var result = new List<IList<int>>();
        int x = 1, y = 1000;
        
        while (x <= 1000 && y >= 1) {
            int val = customfunction.f(x, y);
            if (val == z) {
                result.Add(new List<int> {x, y});
                x++;
                y--;
            } else if (val < z) {
                x++;
            } else {
                y--;
            }
        }
        
        return result;
    }
}

var findSolution = function(customfunction, z) {
    const result = [];
    let x = 1, y = 1000;
    
    while (x <= 1000 && y >= 1) {
        const val = customfunction.f(x, y);
        if (val === z) {
            result.push([x, y]);
            x++;
            y--;
        } else if (val < z) {
            x++;
        } else {
            y--;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
双指针法O(1000) = O(1)O(1)
暴力枚举O(1000²) = O(1)O(1)
二分查找O(1000 × log 1000) = O(1)O(1)

说明：由于题目限制了搜索范围在 1000 以内，所以复杂度可以看作是常数级别。在实际的大数据范围下，双指针法的时间复杂度为 O(n)，其中 n 是搜索范围的大小。