记得小学有道智力题,十个锁,十把钥匙,问你至少试几次,能把对应锁和钥匙配对上?
答:
9次,为啥不是10次,因为最后一次不用试了,可以直接确定。
额,说这些,只是想说,这两道题都需要多重嵌套循环枚举,每层循环枚举都是想找到一个符合条件的数字。
为了不超时,我们可以少一重循环,比如,我们是要确定四个数,理论上是四重循环
但是优化一下,只需要三重循环,最后一个数字按照题目要求,直接算出来,而不需要自己去循环枚举
但是呢,有些时候只少一重循环可能还是不够(由于早年蓝桥暴力杯,上面两题都可以那样暴力ac),循环还是太多
我们需要考虑空间换时间
在四平方和这道题中,我们可以这样优化
先只进行两重循环,然后用结构体,存好每次两重循环的各自变量的值,以及它们的平方和。循环完后针对它们的平方和sort一下,为后面的二分查值做准备,其实就相当于个预处理数组,后面重新再来两重循环,在这个二重循环里面,每次用二分查找查到符合题意的值(也是开始提到的那种思路,先枚举,然后根据枚举结果和题目要求,计算剩下需要的值,然后二分查找预处理的数组找到相应各部分变量的值)
这就是枚举预处理部分数据做成结构体数组,然后再枚举并根据题意反推所需的值,并且用二分查预处理数组的值所对应变量的做法
那么同样的,你可以直接用哈希表存(本题使用哈希表存的话,key是平方和,由于枚举的方式,平方和不会重复,也就是不会出现重复key),那样的话,后面查找直接n(1),可比二分法快多了。
另外提一下,这道题暴力比优化的快(这么说吧,优化只是优化上限,下限不是算法考虑的事,而这道题恰恰就是在下限那里,所以暴力更快些)