比较容易想到一个四重循环的暴力破解办法,第一重循环判断第i个数是不是好数,第二,三,四重循环分别跑第一个数,第二个数和第三个数,但是由于n <= 5000,所以这个方法会TLE,考虑优化,这边注意到时间复杂度是支持On²logn的,而且第一重循环基本上优化不了,那动刀也只是在第二三四重循环上,我们观察第二三四重循环的本质,比较好想一个On3logn的优化方法,第四重循环变set,但是还不够,接着想,我们已知当前值a[i],和第二重循环a[j], 那么我只想知道前i – 1个数中存不存在可复两数和为a[i] –
a[j],所以我们可以优化掉第三四维,开个set来存储之前所有的两数和,时间复杂度On²logn,这样这题就通过了。
细节:注意到是之前所有元素的两数和,所以更新set操作一定是在更新ans操作后,而且每个数可复用,所以ai + ai的值你也要放进set里;还卡set,直接unordered_set