[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)

代码:

public static ArrayList<Integer> longestArith (int[] items) {
        ArrayList<Integer> res = new ArrayList<>();
        Arrays.sort(items);
        int[][] matrix = new int[items.length][items.length];
        int maxLength = 0, maxInc = -1, last = -1;

        for (int i = 1; i < items.length - 1; i++)
        {
            int j = i - 1, k = i + 1;
            while (j >= 0 && k < items.length)
            {
                if (items[j] + items[k] > items[i] * 2)
                    j--;
                else if (items[j] + items[k] < items[i] * 2)
                    k++;
                else
                {
                     matrix[i] [k] = matrix[j][i] == 0 ? 3 : matrix[j][ i] + 1;

                    if (matrix[i][k] > maxLength)
                    {
                        maxLength = matrix[i][ k];
                        last = items[k];
                        maxInc = items[i] - items[j];
                    }

                    j--; k++;
                }
            }
        }
        for (int i = 0; i < maxLength; i++) {
            res.add(last);
            last -= maxInc;
        }
        return res;
    }