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;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://hanquan.blog.csdn.net/article/details/125638757
内容来源于网络,如有侵权,请联系作者删除!