[Google] Longest Arithmetic Sequence 求最长等差数列

这题是我3年前面G家的原题.所以就写上google, 估计这么简单的题g家再也不会问了. 前几天朋友面G家, 已经上模拟退火了, 我也不知道当场白板模拟退火是什么感觉. 不过听说某神牛能IOI就当场写神经网络, 我也就感叹人和牛的差距比人和人的差距都大.

这题其实就是3-sum问题, code改了改就可以了. 所以想想g家onsite,出个3sum, 刷Leetcode的孩子们不要太高兴了, 是不是很良心. 不过写出来代码还是很容易bug的, 然后问时间复杂度,因为求的不是最长的长度, 而是数列, 所以是3-sum-hard 问题. 必然O(n2), 前几天听说有人破了这个hard bound, 不知道是不是真的. 也没关注.

具体思路就是从前往后扫, 如果没排序, 先排序一下,扫的时候, 让游标i在中间, 前边是j, 后边是k, 所以满足, 0<= j < i < k < Array.length, 然后i从1开始往后扫到Array.length-2, 因为j和k是从i初始化的, 每次i走一步, j往后扫,k往前扫, 所以总体的复杂度是O(n2)

代码: