首先先看你给出的LeetCode问题解法代码：

def findOptimalRadius(houses, heaters): 
    houses.sort() 
    heaters.sort() 
    last = len(heaters) - 1 
    x1,x2 = 0,0 
    res = 0 
    for house in houses: 
        while x2 < last and house > heaters[x2]: 
            x1, x2 = x2, x2+1 
        dist1,dist2 = abs(heaters[x1] - house), abs(heaters[x2] - house) 
        res = max(res, min(dist1,dist2)) 
    return res 

这是个非常好的问题！很多人刚接触双指针解法时，都会被这种嵌套循环的结构迷惑，误以为时间复杂度是O(N*M)，但实际上这里的while循环有个核心优化点：指针x2只会单向前进，永远不会回退。

我们来一步步拆解执行次数：

• 外层的for循环会遍历每一个房屋，总共执行N次（N是房屋数量）。
• 内层的while循环里，x2从0开始，每次循环只会将x2加1，最多只会走到last（也就是加热器数组的最后一个索引，即M-1）。换句话说，整个算法运行期间，while循环的总执行次数最多是M次——因为x2不可能从M-1往回走，每个加热器最多被访问一次。

举个直观的例子帮助理解：
假设houses = [1,4,6,8,10]，heaters = [3,7,9]：

• 处理house=1：x2=0，1不大于3，while循环不执行。
• 处理house=4：4>3，x2变成1，此时4不大于7，循环停止。
• 处理house=6：6不大于7，while循环不执行。
• 处理house=8：8>7，x2变成2，此时x2等于last（2），循环停止。
• 处理house=10：10>9，但x2已经等于last，while循环不执行。

这里while循环总共只执行了2次，加上for循环的5次，总操作次数是7，接近N+M=5+3=8的规模（最多就是N+M次）。

对比暴力解法（每个房屋都遍历所有加热器找最近距离），那才是O(N*M)的时间复杂度，但这里利用了两个数组已排序的特性，让x2指针只单向移动，完全避免了重复遍历加热器，从而将遍历部分的时间复杂度降到了O(N+M)。

另外补充一点：整个算法的总时间复杂度其实是由排序步骤主导的，即O(N log N + M log M)，因为排序的时间开销远大于后续遍历的O(N+M)。而你提到的空间复杂度差异，主要取决于排序算法的实现（比如Python内置的sort是Timsort，空间复杂度为O(N)和O(M)），所以会有数组已排序和未排序两种情况的区别。

内容的提问来源于stack exchange，提问作者user15102768