Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.
Return the two integers in any order.
Example 1:
Input: num = 8 Output: [3,3] Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.
Example 2:
Input: num = 123 Output: [5,25]
Example 3:
Input: num = 999 Output: [40,25]
Constraints:
1 <= num <= 10^9
给定一个数num，找出所有a*b等于num+1或num+2的(a,b)组合中，a和b的差最小的那个组合。
子问题就是给定一个数num，找出a*b==num的(a,b)组合中，a和b的差最小的组合。根据反证法，a和b必定有一个小于等于sqrt(num)，另一个大于等于sqrt(num)。所以我最开始的做法是，用之前快速求sqrt的方法，计算sqrt(num)，令left和right都等于sqrt(num)，然后判断left*right的积，如果大于num，则–right；否则++left。这样虽然能得到正确结果，但提交后TLE。
百思不得其解，后来看别人的解答，才理解为什么我会TLE。我的解法设置了left和right两个指针，根据乘积的大小关系，left和right都在移动，在某些情况总的移动数会很大。而正确解法是，只设置一个移动指针i，i从sqrt(num)递减，然后判断num是否能整除i，如果能整除，则肯定找到一个因式分解。这种方法相当于我的方法中只移动了left，速度快了不少。在这种解法下，用不用快速sqrt都能AC。
完整代码如下：
class Solution {
public:
int mySqrt(int x)
{
long long y = x;
while (y*y > x)
{
y = (y + x / y) / 2;
}
return y;
}
vector<int> work(int num) {
for (int i = mySqrt(num) + 1; i >= 1; --i) {
if (num%i == 0) {
return { i,num / i };
}
}
return { 1,num };
}
vector<int> closestDivisors(int num) {
vector<int> plus1 = work(num + 1);
vector<int> plus2 = work(num + 2);
if (abs(plus1[1] - plus1[0]) < abs(plus2[1] - plus2[0]))return plus1;
else return plus2;
}
};