四平方和：从暴力到二分的双向逼近

解题思路:

  四平方和问题最简单的解题方式，最开始想到的估计都是暴力法，这里笔者也是先想到这个，用两种不同的语言都试了一下,c++三重循环暴力能过，但python会超时间一个样例，参考代码如下：

a=int(input())#暴力法求四平方和，超时
i=0
j=0
k=0
flag=1
while i*i<=a and flag:
   j=i
   while i*i+j*j<=a and flag:
       k=j
       while i*i+j*j+k*k<=a and flag:
           h=int(a-i**2-j**2-k**2)
           b=int(h**0.5)
           if (b)**2==h:
               print(i,j,k,b,sep=" ")
               flag=0
               break
           k+=1
       j+=1
   i+=1

  我们想要完全通过这一题，就要考虑换一个方法，这里我考虑的是二分法，首先遍历出四个平方数中的后两个，将其存储在一个列表record中，这里主要的一个思路就是用空间换时间，毕竟现在空间存储技术越来越发达，对于空间复杂度的要求越来越低，这里完全可以采用这种方式牺牲空间复杂度来换取时间复杂度。存储完后两个平方数之后，再进行前两个平方数的遍历(a-i**2-j**2)，然后检索其是否能在咱们之前存储的对应数值里找到，如果能的话，则为我们要找的对应平方数,这里检索的过程利用二分求解：

a=int(input())
record=[]
for i in range(int(a**0.5)+1):
   for j in range(i,int((a-i*i)**0.5)+1):
       record.append((i*i+j*j,i,j))
record.sort()#别忘了二分需要升序排序
for i in range(int(a**0.5)+1):
   for j in range(i, int((a - i * i) ** 0.5) + 1):
       t=a-i*i-j*j
       l=0
       r=len(record)-1
       while l<r:#检索record中是否有对应的前两项平方和
           mid=(l+r)//2
           if record[mid][0]>=t:
                r=mid
           else:
                l=mid+1
       if record[l][0]==t:#检索到的话就输出，退出程序，检索到的第一个即为字典序最小的，为节省时间直接exit
           print(i,j,record[l][1],record[l][2],sep=" ")
           exit()

  这里有一个需要严格注意的细节，就是二分的时候尽量采用向左逼近的二分方法，避免mid+1,不然的话容易时间复杂度过高，虽然这个理论上没什么根据，但是根据刷题的经验来看是这样的