lc-1027-longest-arithmetic-sequence.org

LC 1027. 最长等差数列

https://leetcode-cn.com/problems/longest-arithmetic-sequence/

我们使用两重循环(i,j)去查找A[i], A[j]开头的等差数列，但是一旦发现k是后面一个元素的话，那么可以将(j,k)标记已经访问，因为(i,j)开头产生的等差数列长度更长。这种经常下面经常会有三重循环的错觉。

然后得到i,j之后，查找下一个k有两种方法，我记得这个两种方法之前也写过，具体我忘记了是哪题里面提到的。

• 将值为A[k]的所有k位置记录下来，然后使用二分搜索查找第一个>j的位置
• 将(A[k], k)存入TreeSet, 然后使用 `ceiling(A[k], j+1)` 去查找（但是python没有对应实现）

这种情况下面使用Java还是更好懂

---

class Solution:
    def longestArithSeqLength(self, A: List[int]) -> int:
        from collections import defaultdict
        nums = defaultdict(list)
        n = len(A)

        for i in range(n):
            x = A[i]
            nums[x].append(i)

        def find_next(exp, i):
            xs = nums[exp]
            s, e = 0, len(xs) - 1
            while s <= e:
                m = (s + e) // 2
                if xs[m] > i:
                    e = m - 1
                else:
                    s = m + 1
            # print(exp, xs, i, s)
            if s >= len(xs):
                return None
            return xs[s]

        visited = set()
        ans = 2
        for i in range(n):
            for j in range(i + 1, n):
                d = A[j] - A[i]
                if (i, j) in visited:
                    continue
                visited.add((i, d))
                sz = 2
                exp = A[j] + d
                k = j
                while True:
                    k2 = find_next(exp, k)
                    if k2 is None:
                        break
                    visited.add((k, k2))
                    sz += 1
                    exp += d
                    k = k2
                ans = max(ans, sz)
        return ans

---

class Item implements Comparable<Item> {
    int value;
    int index;
    public Item(int value, int index) {
        this.value = value;
        this.index = index;
    }
    public int compareTo(Item x) {
        if (value != x.value) {
            return value - x.value;
        }
        return index  - x.index;
    }
    public String toString() {
        return String.format("(value=%d, index=%d)", value, index);
    }
}
class Solution {
    public int longestArithSeqLength(int[] A) {
        TreeSet<Item> ts = new TreeSet<>();
        for (int i = 0; i < A.length; i++ ){
            int x = A[i];
            ts.add(new Item(x,i));
        }
        int[][]visited = new int[A.length][];
        for(int i=0;i<A.length;i++) {
            visited[i] = new int[A.length];
        }
        int ans = 2;
        for(int i=0;i<A.length;i++) {
            for (int j=i+1;j<A.length;j++) {
                if (visited[i][j] == 1) {
                    continue;
                }
                visited[i][j] = 1;
                int d = A[j] - A[i];
                int exp = A[j] + d;
                int sz = 2;
                int k = j;
                while (true) {
                    Item x = ts.ceiling(new Item(exp, k+1));
                    // System.out.printf("search item. exp = %d, k+1 = %d, x = %s\n", exp, k+1, x);
                    if (x != null && x.value == exp) {
                        sz += 1;
                        exp += d;
                        int k2 = x.index;
                        visited[k][k2] = 1;
                        k = k2;
                    } else {
                        break;
                    }
                }
                ans = Math.max(ans, sz);
            }
        }
        return ans;
    }
}