題目描述：

給你一個函數(shù) f(x, y) 和一個目標(biāo)結(jié)果 z，函數(shù)公式未知，請你計算方程 f(x,y) == z 所有可能的正整數(shù) 數(shù)對 x 和 y。滿足條件的結(jié)果數(shù)對可以按任意順序返回。

盡管函數(shù)的具體式子未知，但它是單調(diào)遞增函數(shù)，也就是說：

f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
函數(shù)接口定義如下：

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);
};
你的解決方案將按如下規(guī)則進(jìn)行評判：

判題程序有一個由 CustomFunction 的 9 種實(shí)現(xiàn)組成的列表，以及一種為特定的 z 生成所有有效數(shù)對的答案的方法。
判題程序接受兩個輸入：function_id（決定使用哪種實(shí)現(xiàn)測試你的代碼）以及目標(biāo)結(jié)果 z 。
判題程序?qū){(diào)用你實(shí)現(xiàn)的 findSolution 并將你的結(jié)果與答案進(jìn)行比較。
如果你的結(jié)果與答案相符，那么解決方案將被視作正確答案，即 Accepted 。

示例 1：

輸入：function_id = 1, z = 5
輸出：[[1,4],[2,3],[3,2],[4,1]]
解釋：function_id = 1 暗含的函數(shù)式子為 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 暗含的函數(shù)式子為 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 的范圍內(nèi)。
在 1 <= x, y <= 1000 的前提下，題目保證 f(x, y) 是一個 32 位有符號整數(shù)。

解題思路一：雙指針。首先我們不管f是什么，即function_id等于什么不管。但是我們可以調(diào)用customfunction中的f函數(shù)，然后我們遍歷x,y(1 <= x, y <= 1000)只要f(x,y)=z的(x,y)即是我們需要的答案。然后我們從x=1與y=1000開始遍歷。此時有三種情況：

• 情況一:f(x,y)>z，那么固定y，繼續(xù)增大x，函數(shù)值也會繼續(xù)增大。顯然不符合題意。故將y減1縮小答案。

• 情況二:f(x,y)<z，那么固定y，繼續(xù)增大x，函數(shù)值也會繼續(xù)增大。顯然是符合題意的。故將x加1增大答案。

• 情況三:f(x,y)=z，先將（x,y）加入答案，然后固定y，繼續(xù)增大x，函數(shù)值也會繼續(xù)增大。顯然是不符合題意的。故將y減1縮小答案。（類似情況一）

/** // This is the custom function interface.* // You should not implement it, or speculate about its implementation* class CustomFunction {* public:*     // 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)*     int f(int x, int y);* };*/class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> ans;int x=1,y=1000;while(x<=1000&&y>=1){int t=customfunction.f(x,y);if(t>z) --y;else if(t<z) ++x;else ans.push_back({x++,y--});}return ans;        }
};

時間復(fù)雜度：O(2C)//C=1000
空間復(fù)雜度：O(1)

解題思路二：二分查找。枚舉x，二分查找y。找到之后x增大因?yàn)閒對x,y遞增故之后的y必小于middle。即f(x,middle)=z若要f(x+1,y)=z那么y必小于middle;對右邊界的優(yōu)化。

/** // This is the custom function interface.* // You should not implement it, or speculate about its implementation* class CustomFunction {* public:*     // 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)*     int f(int x, int y);* };*/class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;int left = 1, right = 1000;//右邊界right會不斷縮小for(int x=1;x<=1000;x++) {//枚舉x，二分查找yleft = 1;//每次左邊界left從1開始while(left<=right) {int middle=(left+right)/2;int t=customfunction.f(x, middle);if(t==z){res.push_back({x, middle});right=middle-1;//縮小右邊界break;//break之后x增大因?yàn)閒對x,y遞增故之后的y必小于middle。即f(x,middle)=z若要f(x+1,y)=z那么y必小于middle;}else if(t<z) left=middle + 1;else right=middle-1;//縮小右邊界}//其實(shí)發(fā)現(xiàn) right == 0 了可以直接返回}return res;}
};

時間復(fù)雜度：O(C+logC)//C=1000
空間復(fù)雜度：O(1)

解題思路三：0