本文发表在 rolia.net 枫下论坛我从网上找的了这道题的思路。下面是我的java code


是从下面这个链接的思路里，改写的。
http://codercareer.blogspot.ca/2014/03/no-53-longest-arithmetic-sequence.html


import java.io.Console;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ASeries {

public int longest(int[] values) {

// sort the array
Arrays.sort(values);

Map<Integer, List<Pair>> hashTable = buildHashTable(values);

return analyze(hashTable, values.length);
}

/*

for an array {3, 8, 4, 5, 6, 2, 2}, group the pars like this
differenece 0: (2,2)
difference 1: (2,3), (3,4), (4,5),(5,6)

so we need a hash table to store the information, the key is the difference.
the value is the indexes of the pairs(not values)
*/
private Map<Integer, List<Pair>> buildHashTable(int[] values) {

Map<Integer, List<Pair>> hashTable = new HashMap<Integer, List<Pair>>();

for (int i = 0; i < values.length; i++) {
for (int j = i + 1; j < values.length; j++) {

Pair pair = new Pair();
pair.setFirst(i);
pair.setSecond(j);

int diff = values[j] - values[i];
if (hashTable.containsKey(diff)) {
hashTable.get(diff).add(pair);
} else {
List<Pair> newValue = new ArrayList<Pair>();
newValue.add(pair);
hashTable.put(diff, newValue);
}
}
}

return hashTable;

}

/*
in this method, we need to get the length of the pairs with each difference.

A list of pairs with difference k is got given a key k in the hash table.
If an element A[i] is mth element is an arithmetic sequence with a common difference k, and there is a pair (A[i], A[j]) (j>i) in the list of pairs,
the element A[j] should be the m+1th elemement in the arithmetic sequence.

*/
private int analyze(Map<Integer, List<Pair>> hashTable, int lengthOfNumbers) {

int maxLength = 0;
for (int key : hashTable.keySet()) {
int[] lengths = new int[lengthOfNumbers];

for (int i = 0; i < lengthOfNumbers; i++) {
lengths[i] = 1;
}

for (Pair pair : hashTable.get(key)) {
lengths[pair.getSecond()] = lengths[pair.getFirst()] + 1;
}

for (int length : lengths) {
if (length > maxLength) {
maxLength = length;
}
}
}

return maxLength;
}

private static void test(String testName, int[] numbers, int expected) {

ASeries as = new ASeries();

if (as.longest(numbers) == expected) {
System.out.println(String.format("%s passed.", testName));
} else {
System.out.println(String.format("%s failed.", testName));
}
}

private static void test1() {
int[] numbers = {3, 8, 4, 5, 6, 2, 2};
int expected = 5;
test("test1", numbers, expected);
}

private static void test2() {
int[] numbers = {-1, -5, 1, 3};
int expected = 3;
test("test2", numbers, expected);
}

private static void test3() {
int[] numbers = {-10, -20, -10, -10};
int expected = 3;
test("test3", numbers, expected);
}

public static void main(String[] args) {
test1();
test2();
test3();
}

}

class Pair {
private int first;
private int second;

public int getFirst() {
return first;
}

public void setFirst(int first) {
this.first = first;
}

public int getSecond() {
return second;
}

public void setSecond(int second) {
this.second = second;
}
}


不知道哪里有这样的活动，让我们这些在多伦多的IT猥琐男，每月聚一下，大家交流，交流啊？哪位大侠有这样振臂一呼的能力？更多精彩文章及讨论，请光临枫下论坛 rolia.net