leetcode 873. Length of Longest Fibonacci Subsequence | 873. 最长的斐波那契子序列的长度

题目

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/

题解

被注释掉的部分是负优化。本意是O(n^2*logM)->O(n^2)，然而对set做C(2,992)=491536次insert，比优化掉的logM开销还大。

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        HashSet<Integer> set = new HashSet<>();
        for (int a : arr) {
            set.add(a);
        }

        int result = 0;
        // HashSet<String> visited = new HashSet<>(); // "1,2"
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x = arr[i];
                int y = arr[j];
                // String pair = x + "," + y;
                int count = 2;
                // if (!visited.contains(pair)) {
                    // visited.add(pair);
                    while (set.contains(x + y)) {
                        int next = x + y;
                        count++;
                        x = y;
                        y = next;
                        // visited.add(x + "," + y);
                    }
                // }
                result = Math.max(result, count);
            }
        }
        return result > 2 ? result : 0;
    }
}