LeetCode题解：1237. 找出给定方程的正整数解，双指针，详细注释

[chencl1986]

原题链接： https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/

解题思路：

1. 回顾题目给出的两个条件：
   • f(x, y) < f(x + 1, y)
   • f(x, y) > f(x, y - 1)，由f(x, y) < f(x, y + 1)变化而来
2. 如果我们先声明let x = 1, y = 1000，相对于z有以下几种情况：
   • 当f(x, y) < z时，只需要将x++
   • 当f(x, y) > z时，只需要将y--
   • 当f(x, y) === z时，当前x和y是一个解
3. 当x === 1000且y === 1时，所有的解都已经查找出来

/**
 * @param {CustomFunction} customfunction
 * @param {integer} z
 * @return {integer[][]}
 */
var findSolution = function(customfunction, z) {
  let result = [] // 存储结果

  for (
    // x默认值为左边界，y默认值为右边界
    let x = 1, y = 1000;
    // x向右移动，y向左移动，x和y都到达边界时，表示已经查找到所有结果，退出循环
    x <= 1000 && y >= 1;
  ) {
    // 计算当前x、y对应的结果
    const subResult = customfunction.f(x, y)

    // f(x, y) < f(x + 1, y)
    if (subResult < z) {
      x++
    }
    // f(x, y) > f(x, y - 1)
    else if(subResult > z) {
      y--
    } else {
      // f(x, y) === z，存储[x, y]，并移动x和y
      result.push([x++, y--])
    }
  }

  return result
};

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$。返回值不计入空间复杂度