【C# 每日一题2】求最长等差数列

Question

题目需求：
在一个升序排列好的数列里面找到最长的等差数列例子：1 3 5 6 8 9 10 12 13 14
子数列有(两项的不在列举）
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
.....得出的最长的等差数列应该是：6 8 10 12 14大家各抒己见，踊跃发言，写一下自己的想法吧！每日一题1 得到了版主的推荐，我们有了一个不错的开始，希望大家都加入进来，一起讨论，共同进步！！

Answer 1

补充一点，输入时候的设置，让我容易去测试程序：
首先输入 n 代表数组里的数据个数
之后输入n个数据
输出最长等差数列。。
例如：
Input：
10
1 3 5 6 8 9 10 12 13 14
Output：
6 8 10 12 14

Answer 2

在补充一下，数据量 n < 10000
我们可以假定输入的数据就是排序好的！

Answer 3

计算机吗，当然是穷举了，
for (int i = 0; i < length; i++)
{
  for (int j = 0; j < length; j++)
  {
    //根据i，j下标取出两个数，假设就是等差数列的前两位，那么接着再求后面的。
    //如果优化，可以记下等差的差值，如果发现这个差值已经处理过，那直接就可以跳过
  }
}

Answer 4

#include "stdio.h"
#include <map>
using namespace std;#define MAX_LEN 1000
int data[MAX_LEN];
int length;
int best;
int bestdelta;
int beststart;void Run()
{
map<int,int> alldata;
map<int,int> useddelta;
scanf("%d",&length);
for(int i = 0;i < length;i++)
{
scanf("%d",data+i);
alldata[data[i]] = 0;
} if(length == 1)
{
printf("%d\n",data[0]);
return;
} best = 2;
bestdelta = data[1]-data[0];
beststart = data[0];
for(int i = 0;i < length-best+1;i++)
{
useddelta.clear();
for(int j = 0;j <= i;j++)useddelta[data[i]-data[j]] = 0;
for(int j = i+1;j < length-best+2;j++)
{
if(useddelta.find(data[j]-data[i]) != useddelta.end())continue;
int delta = data[j]-data[i];
int curlen = 2;
int curdata = data[j];
while(true)
{
if(alldata.find(curdata+delta) != alldata.end())
{
curlen++;
curdata += delta;
}
else break;
}
if(curlen > best)
{
best = curlen;
bestdelta = delta;
beststart = data[i];
}
}
}
for(int i = 0;i < best-1;i++,beststart += bestdelta)printf("%d ",beststart);
printf("%d\n",beststart);
}
int main()
{
Run();
return 0;
}

Answer 5

        static void Main(string[] args)
        {
            List<NumListHeader> allList = new List<NumListHeader>();
            string[] s = Console.ReadLine().Split(' ');
            NumListBody max = null;
            int[] allNum = s.ToList().ConvertAll<int>((x) => { return int.Parse(x); }).ToArray();
            allNum.ToList().ForEach((n)=>{                allList.ForEach((l) => {
                    bool newlist = l.bodys.Count==0;
                    l.bodys.ForEach((b) => {
                        if (n == b.Step * b.length + l.Start)
                        {
                            b.length++;
                            if (max == null || b.length > max.length)
                            {
                                max = b;
                            }
                        }
                        else if (n > b.Step * b.length + l.Start)
                        {
                            l.bodys.Remove(b);
                        }
                        else
                        {
                            newlist = true;
                        }
                    });
                    if (newlist)
                    {
                        l.bodys.Add(new NumListBody() { length =2, Step = n-l.Start, Start = l.Start  });
                    }
                });
                allList.Add(new NumListHeader() { Start = n });
            });
            Console.WriteLine("start:{0},step:{1},length:{2}", max.Start, max.Step, max.length);
            Console.Read();
        }
    }
    class NumListBody
    {
        public int Start;
        public int Step;
        public int length;
    }
    class NumListHeader
    {
        public NumListHeader()
        {
            bodys = new List<NumListBody>();
        }
        public int Start;
        public List<NumListBody> bodys;
    }

Answer 6

有个bug，重发一次    class Program
    {
        static void Main(string[] args)
        {
            List<NumListHeader> allList = new List<NumListHeader>();
            string[] s = Console.ReadLine().Split(' ');
            NumListBody max = null;
            s.ToList().ConvertAll<int>((x) => { return int.Parse(x); }).ForEach((n)=>{                allList.ForEach((l) => {
                    bool newlist = l.bodys.Count==0;
                    for (int i = l.bodys.Count - 1; i >= 0; i--)
                    {
                        NumListBody b = l.bodys[i];
                        if (n == b.Step * b.length + b.Start)
                        {
                            b.length++;
                            if (max == null || b.length > max.length)
                            {
                                max = b;
                            }
                        }
                        else if (n > b.Step * b.length + b.Start)
                        {
                            l.bodys.Remove(b);
                        }
                        else
                        {
                            newlist = true;
                        }
                    }
                    if (newlist)
                    {
                        l.bodys.Add(new NumListBody() { length =2, Step = n-l.Start, Start = l.Start  });
                    }
                });
                allList.Add(new NumListHeader() { Start = n });
            });
            Console.WriteLine("start:{0},step:{1},length:{2}", max.Start, max.Step, max.length);
            Console.Read();
        }
    }
    class NumListBody
    {
        public int Start;
        public int Step;
        public int length;
    }
    class NumListHeader
    {
        public NumListHeader()
        {
            bodys = new List<NumListBody>();
        }
        public int Start;
        public List<NumListBody> bodys;
    }

Answer 7

算法基本上在注释中解释清楚了。总的思想是用liveSeq追踪所有可能的等差序列，把所有可能的在n结束的序列记录在liveSeq的第n个位置。
#include <iostream>
#include <cstring>
#include <utility>
#include <vector>using namespace std;int n;
int a[10001];
int flag[10001];
/**
 * liveSeq[i] 是一个由（d,l）组成的对子，该数组表示在给定的序列中有差为d,长为l,结束在i的等差序列。
 * 处理完值为n的项后，该数组中总的对子的个数为O(nlgn)。
 */
vector< pair<int, int> > liveSeq[10001];int main() {
  memset(flag, 0, sizeof(flag));
  cin >> n;
  //n = 10000;
  
  for (int i=0; i<n; i++) {
    cin >> a[i];
    //a[i] = i;
    flag[a[i]] = 1;
  }  int maxai = a[n-1];
  
  int maxlength = 2;
  int maxEnd = a[1];
  int maxDiff = a[1]-a[0];
  
  for (int i=0; i<n; i++) {
    int next = a[i];
    // a[i]可以和a[j]（j<i）构成新的等差序列
    // 下面循环中注1处的检测条件是根据这样一个事实：
    // 如果a[i]-a[j]太大的话，即使这个序列能一直延伸到最大值，也不可能有足够多的项来超过
    // 已有的maxlength。
    for (int j=i-1; j>=0; j--) {
      if (maxlength> 2 and next-a[j] > (maxai-next)/(maxlength-2)) { //注1
          break;
      }
      if (flag[2*a[j]-a[i]] == 0 and (2*a[i]-a[j]<=maxai) and (flag[2*a[i]-a[j]] == 1)) {
        liveSeq[2*a[i]-a[j]].push_back(make_pair(a[i]-a[j], 3));
      }
    }
    // 扩展原来在next结束的数列
    for (int j = 0; j<liveSeq[next].size(); j++) {
      pair<int, int> seq = liveSeq[next][j];
      if (next+seq.first <= maxai and flag[next+seq.first] == 1) {
        // 可以扩展
        seq.second += 1;
        liveSeq[next+seq.first].push_back(seq);
      } else {
        // 不能再扩展了，看它的长度是否破了记录
        if (seq.second > maxlength) {
          maxlength = seq.second;
          maxEnd = next;
          maxDiff = seq.first;
        }
      }
    }
    // 原来结束在next的序列或者在下一站获得了新生，或者已经被盖棺定论了，可以清除它们的记录了
    liveSeq[next].clear();
  }
  // print the sequence
  int start = maxEnd - (maxlength-1)*maxDiff;
  while (start <= maxEnd) {
    cout << start << " ";
    start += maxDiff;
  }
  cout << endl;
}

Answer 8

O(n^2)*log(n)的方法，进行了优化，高手！

Answer 9

12楼代码刚才测试了一下，在小数据范围内是正确的，但是数据一旦大于10000，问题就出现了
问题出现在我的身上，可能是题目没有说清楚
数据范围是在int范围内，但是数据量限定在了10000以内！
12是理解错了我的意思，抱歉了！希望改一下代码！大家共同讨论一下！

Answer 10

前段时间刚好想过这个问题，有2个方法，一个是n^2空间,n^2时间的，一个是m*n/k时间（m为最大数与最小数的差，k为最长序列的长度），O(n)空间的，以上两个方法要求数据中没有重复的元素，并且需要先对数据排序不过个人感觉应该有更好的方法        public static void Solve2(int[] 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++;
                    }
                }
            }            Console.WriteLine("{0} {1} {2}", maxLength, maxInc, last);
        }        public static void Solve1(int[] items)
        {
            Dictionary<int, int> hash = new Dictionary<int, int>();
            int max = items.Max() - items.Min();
            int maxLength = 2, maxInc = -1, last = -1;            for (int inc = 1; inc < max; inc++)
            {
                if (inc * maxLength > max)
                    break;                hash.Clear();
                hash.Add(items[0], 1);                for (int i = 1; i < items.Length; i++)
                {
                    if (hash.ContainsKey(items[i] - inc))
                    {
                        int value = hash[items[i] - inc];
                        hash.Remove(items[i] - inc);
                        hash.Add(items[i], value + 1);                        if (value + 1 > maxLength)
                        {
                            maxLength = value + 1;
                            maxInc = inc;
                            last = items[i];
                        }
                    }
                    else if (!hash.ContainsKey(items[i]))
                        hash.Add(items[i], 1);
                }
            }            Console.WriteLine("{0} {1} {2}", maxLength, maxInc, last);
        }

Answer 11

NumListBody储存一个数列的起始 步长 长度，NumListHeader储存所有以同一数字开始的数列，遍历每一个数n，检查n和全部比它小的数m，尝试将n归入所有以m开头的数列中，如不能归入所有m开头数列，则增加一个m,n为起始2元素的数列，如此至最后一个数字，找出其中最长的，优化的方法主要是检查一个数列如果无法增长或者即使增长也无法达到目前最长数列时，就放弃此数列。

Answer 12

我就喜欢这种讲思路的，不喜欢看代码。思路明确了，代码就是小case了。

Answer 13

        static void Main(string[] args)
        {
            int[] array = new int[] { 1, 3, 5, 6, 8, 9, 10, 12, 13, 14, 20, 22, 23, 24, 25, 26, 28, 30, 34, 38, 42, 46, 50 };
            ISet<Int32> set = new HashSet<Int32>(array);            for (int length = array.Length; length > 2; length--)
            {
                for (int startPos = 0; startPos + length <= array.Length; startPos++)
                {
                    int first = array[startPos];
                    int diff = array[array.Length - 1] - first;
                    int maxStep = diff / (length - 1);
                    for (int step = 1; step <= maxStep; step++)
                    {
                        bool valid = true;
                        for (int i = 1; i < length; i++)
                        {
                            int x = first + i * step;
                            if (!set.Contains(x)) 
                            {
                                valid = false;
                                break;
                            }
                        }                        if (valid)
                        {
                            Console.WriteLine("length: {0}, first: {1}, step: {2}",
                                    length,
                                    first,
                                    step);
                            goto end;
                        }
                    }
                }
            }
            
            end:
            Console.ReadKey();
        }

Answer 14

又见大牛，欢迎java版大牛参与！双层for循环下，枚举不同的差值，用hash简化查找，希望我理解对了！

Answer 15

对C#不熟，不知道C#对应java的continue label是哪个？这里有个完整打印的，可以说明解题思路:
        static void Main(string[] args)
        {
            int[] array = new int[] { 1, 3, 5, 6, 8, 9, 10, 12, 13, 14/*, 20, 22, 23, 24, 25, 26, 28, 30, 34, 38, 42, 46, 50 */};
            ISet<Int32> set = new HashSet<Int32>(array);            for (int length = array.Length; length > 2; length--)
            {
                Console.WriteLine("最大可能长度{0}", length);
                Console.WriteLine("--------------------------------------------------------");
                for (int startPos = 0; startPos + length <= array.Length; startPos++)
                {
                    int first = array[startPos];
                    Console.WriteLine("\t第一个元素：{0}", first);
                    int diff = array[array.Length - 1] - first;
                    int maxStep = diff / (length - 1);
                    for (int step = 1; step <= maxStep; step++)
                    {
                        Console.WriteLine("\t\t步长：{0}", step);
                        Console.Write("\t\t数列：{0}", first);
                        bool valid = true;
                        for (int i = 1; i < length; i++)
                        {
                            int x = first + i * step;
                            if (!set.Contains(x)) 
                            {
                                Console.WriteLine(", 找不到{0}", x);
                                valid = false;
                                break;
                            }
                            Console.Write(", {0}", x);
                        }                        if (valid)
                        {
                            Console.WriteLine("找到了！length: {0}, first: {1}, step: {2}",
                                    length,
                                    first,
                                    step);
                            goto end;
                        }
                    }
                }
            }
            
            end:
            Console.ReadKey();
        }
    }

Answer 16

问了一下，同事说是goto！
不熟悉C#没有关系，这里面的代码还有c++的呢，欢迎参与，代码可以用自己拿手的！

Answer 17

goto 不等价吧
    outer: for (int i = 0; i < 10; i++) {
      System.out.println(i);
      for (int j = i; j < 10; j++) {
        if (j == 3) {
          continue outer;
        }
        // lots of lines to do sth.
      }
    }
直接continue换goto会死循环的，少了i++的执行。就是因为找不到这个continue label,想了半天，才想到用个flag，老实说有点蛋疼。

Answer 18

如果你想在一个for循环中继续执行就是continue
如果想要跳出这个for循环，break
别的还真的不知道！

Answer 19

知道了：
outer: for (;;)
{
  inner: for (;;)
  {
     if (condition)
     {
        goto outerEnd; // 等价于continue outer;
     }
  }  // lots of lines to do sth.
  outerEnd: {}
}

Answer 20

我也来凑热闹
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 10000000;
int f[MaxN + 2];
int pre[MaxN + 2];int a[MaxN];
int best;
int bestAns_i;
int bestAns_d;
int N;
int count(int d) {
    int i;
    f[0] = 1;
    for (i = 1; i < N; ++i) {
        f[i] = 1;
        pre[i] = -1;
        int * p = lower_bound(a + 0, a + i, a[i] -d);
        if (p != a + i && *p == a[i] - d) {
            int pos = p -a;
            f[i] = f[pos] + 1;
            pre[i] = pos;
        }        if (f[i] > best) {
            best = f[i];
            bestAns_i = i;
            bestAns_d = d;
        }
    }    return 0;
}
void showAns() {
    int n = a[bestAns_i];
    while(binary_search(a+0,a+bestAns_i + 1, n) ) {
        printf("%d ", n);
        n -= bestAns_d;
    }
    printf("\n");
}
void run() {
    int i = 0;
    int tmp;
    int max = -99999999, min = 99999999;
    while(1) {
        if (scanf("%d", &tmp) != 1) break;
        a[i] = tmp;
        ++i;
        max = std::max(max, tmp);
        min = std::min(min, tmp);
    }
    N = i;    int maxD = max - min;
    best = -99999999;
    for (int d = 0; d <= maxD; ++d) {
        count(d);
    }    printf("%d\n", best);
    showAns();
}int main() {
    run();
    return 0;
}

Answer 21

n^2空间,n^2时间这个简单，很容易理解；
一个是m*n/k时间（m为最大数与最小数的差，k为最长序列的长度），O(n)空间的 这个一下没想清楚……

Answer 22

更正一下输出格式：
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 10000000;
int f[MaxN + 2];
int pre[MaxN + 2];int a[MaxN];
int best;
int bestAns_i;
int bestAns_d;
int N;
int count(int d) {
    int i;
    f[0] = 1;
    for (i = 1; i < N; ++i) {
        f[i] = 1;
        pre[i] = -1;
        int * p = lower_bound(a + 0, a + i, a[i] -d);
        if (p != a + i && *p == a[i] - d) {
            int pos = p -a;
            f[i] = f[pos] + 1;
            pre[i] = pos;
        }        if (f[i] > best) {
            best = f[i];
            bestAns_i = i;
            bestAns_d = d;
        }
    }    return 0;
}
void showAns() {
    int n = a[bestAns_i];
    while(binary_search(a+0,a+bestAns_i + 1, n) ) {
        //~ printf("%d ", n);
        n -= bestAns_d;
    }
    n += bestAns_d;
    while(n <=  a[bestAns_i]) {
        printf("%d ", n);
        n += bestAns_d;
    }
    printf("\n");}
void run() {
    int tmp;
    int max = -99999999, min = 99999999;
    scanf("%d", &N);
    int i;
    for (i = 0; i < N; ++i) {
        scanf("%d", &a[i]) ;
        tmp = a[i];
        max = std::max(max, tmp);
        min = std::min(min, tmp);
    }    int maxD = max - min;
    best = -99999999;
    for (int d = 0; d <= maxD; ++d) {
        count(d);
    }    //~ printf("%d\n", best);
    showAns();
}int main() {
    run();
    return 0;
}

Answer 23

假设要求公差为d的最长等差数列
令f(i)表示以a[i]为结尾，d为公差的最长等差数列的长度，规定长度为1的数列也是等差数列。
那么有f(i) = max{f(j) + 1, 1 | j < i 且 a[j] = a[i] - d}
将d枚举，计算出每个f(i)，取最大值

Answer 24

是我想的简单了。修改后的代码在下面。算法和20楼lihanbing讲的差不多，只不过我是储存所有结束在同一个数的子序列。复杂度大概是n^2lgn.
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int n;
int a[10001];
/*  sequence表示一个等差序列，diff是差，length是已找到的最大长度，start是第一项。 */struct sequence {
  int start;
  int diff;
  int length;
  sequence(int s, int d, int l): start(s), diff(d), length(l){ }
};
/*  liveSeq[i]中保存了所有结束在a[i]的等差子序列。 */
vector<sequence> liveSeq[10001];int main() {
  cin >> n;
  
  for (int i=0; i<n; i++) {
    cin >> a[i];
  }  int maxai = a[n-1];
  
  int maxLength = 2;
  int maxStart = a[0];
  int maxDiff = a[1]-a[0];
  
  for (int i=0; i<n; i++) {
    // a[i]可以和a[j]（j<i）构成新的等差序列
    // 下面循环中第二个检测条件是根据这样一个事实：
    // 如果a[i]-a[j]太大的话，即使这个序列能一直延伸到最大值，也不可能有足够多的项来超过
    // 已有的maxLength。
    if (n-i+1 > maxLength) {
      // a[i]之后至少有maxLength项，这样还有可能构造一个长度超过maxLength的序列
      for (int j=i-1; j>=0 and (a[i]-a[j] <= 1.0*(maxai-a[i])/(maxLength-1)); j--) {
        if (!binary_search(a, a+j-1, 2*a[j]-a[i])) {
          // 2*a[j]-a[i], a[j], a[i]不是等差子序列
          int* next = lower_bound(a+i+1, a+n, 2*a[i]-a[j]);
          if (*next == 2*a[i]-a[j]) {
            sequence newseq(a[j], a[i]-a[j], 3);
            liveSeq[next-a].push_back(newseq);
          }
        }
      }
    }    // 扩展原来在a[i]结束的数列    
    vector<sequence> seqs = liveSeq[i];    
    for (int j = 0; j<seqs.size(); j++) {
      sequence seq = seqs[j];
      int *next = lower_bound(a+i+1, a+n, a[i]+seq.diff);
      if (*next == a[i]+seq.diff) {        
        // 可以扩展
        seq.length += 1;
        liveSeq[next-a].push_back(seq);
      } else {
        // 不能再扩展了，看它的长度是否破了记录
        if (seq.length > maxLength) {
          maxLength = seq.length;
          maxStart = seq.start;
          maxDiff = seq.diff;
        }
      }
    }
    // 原来结束在next的序列或者在下一站获得了新生，或者已经被盖棺定论了，可以清除它们的记录了
    liveSeq[i].clear();
  }
  // print the sequence
  for (int i=0; i<maxLength; i++) {
    cout << maxStart << " ";
    maxStart += maxDiff;
  }
  cout << endl;
}

Answer 25

新手，有错请包涵  //最终的计算结果
        static List<int> list = new List<int>();
        //计算方法
        static void newCalc(int[] nums)
        {
            Array.Sort(nums);
            int length = nums.Length;
            //差值
            int sp = 0;
            //计算出的等差队列 第一个元素为 nums[i]
            for (int i = 0; i < length - 1; i++)
            {
                //计算出的等差队列 第二个元素为 nums[j]
                for (int j = i + 1; j < length; j++)
                {
                    //差
                    sp = nums[j] - nums[i];
                    //此次计算出的等差队列
                    List<int> slist = new List<int>();
                    slist.Add(nums[i]);
                    slist.Add(nums[j]);
                    int end = nums[j];
                    for (int n = j + 1; n < length; n++) 
                    {
                        //继续向后找
                        if (nums[n] - end < sp) { continue; }
                        //
                        if (nums[n] - end > sp) { break; }
                        //添加到队列，向后找
                        if (nums[n] - end == sp)
                        {
                            slist.Add(nums[n]);
                            end = nums[n];
                        }
                    }
                    //判断
                    if (slist.Count > list.Count)
                    {
                        list = slist;
                    }
                }
            }
            
        }
        static void Main()
        {
            string str = "1 5 6 9 10 13 14 18 22";
            string[] args = str.Split(' ');
            int[] nums = new int[args.Length];
            for (int i = 0; i < args.Length; i++)
            {
                nums[i] = int.Parse(args[i].Trim());
            }
            newCalc(nums);
            //打印 list集合
            string result = "";
            for (int i = 0; i < list.Count; i++)
            {
                result += list[i].ToString() + ",";
            }
            Console.WriteLine(result);
        }

Answer 26

/*
 * 1.先计算出所有的公差d，存放在数组中
 * 2.从数列的第1项开始，根据数组中的公差生成n个等差数列，存放在ArrayList里
 * 3.ArrayList里长度最大的一项就是所求结果
 * 
 * 由于在LINUX下，不方便配置C#环境，就用java写了。
 */import java.util.ArrayList;
import java.util.HashMap;public class Test {
public static void main(String[] args){
System.out.println(new Seq(new int[]{1,3,5,6,8,9,10,12,13,14}).getArray().toString());
                System.out.println(new Seq(new int[]{1,2,4,6,8,9,12,13,14,16,19,20,22,23,24}).getArray().toString());
}
}class Seq{
int[] num;
Integer[] d;//公差
ArrayList<ArrayList<Integer>> seq;

public Seq(int[] array){
num = array;
}

public ArrayList<Integer> getArray(){
d = getD();
seq = new ArrayList<ArrayList<Integer>>(d.length * d.length);
for(int k = 0;k < d.length;k++){
for(int i = 0;i < num.length;i++){
int n = d[k];
ArrayList<Integer> array = new ArrayList<Integer>();
array.add(num[i]);
for(int j = i;j < num.length;j++){
if(num[i] + n == num[j]){
array.add(num[j]);
n += d[k];
}
}
seq.add(array);
}
}
int max = seq.get(0).size();
int index = 0;
for(int i = 1; i < seq.size();i++){
if(seq.get(i).size() > max){
max = seq.get(i).size();
index = i;
}
}
return seq.get(index);
}
private Integer[] getD(){
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i = 0;i < num.length;i++){
for(int j = i + 1;j < num.length;j++){
int key = j - i;
if(!hm.containsKey(key)){
hm.put(key, 1);
}
}
}
Integer[] array = new Integer[hm.size()];
hm.keySet().toArray(array);
return array;
}
}结果：
[6, 8, 10, 12, 14]
[4, 8, 12, 16, 20, 24]

Answer 27

恩，这样在优化一下能做到O(n^2)*log(n）

Answer 28

暴力解决。http://blog.csdn.net/xiaoxin888888/archive/2011/05/24/6442796.aspx

Answer 29

//用分治法来解决此问题， 只处理了递增等差数列//在右字串中得到最长等差数列后尝试向左扩展
void extendToLeft(int *arr, int lowerbound, 
  /*in out */int *prightsubindex,
  /*in out */int *prightsublen){
int rightequdiff = 0, index = *prightsubindex - 1; if (*prightsublen == 1)
{
if (arr[*prightsubindex - 1] < arr[*prightsubindex])
{
(*prightsubindex) = (*prightsubindex) - 1;
*prightsublen = 2;
}
}
else
{
rightequdiff = arr[*prightsubindex + 1] - arr[*prightsubindex]; for (; index >= lowerbound && arr[index + 1] - arr[index] == rightequdiff; index--); *prightsublen += *prightsubindex - (index + 1); *prightsubindex = index + 1;
}
}//在左字串中得到最长等差数列后尝试向右扩展
void extendToRight(int *arr, int upperbound, 
    int leftsubindex, /*in out */int *pleftsublen)
{
int leftequdiff = 0, index = leftsubindex + *pleftsublen; if (*pleftsublen == 1)
{
if (arr[leftsubindex] < arr[leftsubindex + 1])
*pleftsublen = 2;
}
else
{
leftequdiff = arr[leftsubindex + 1] - arr[leftsubindex]; for (; index <= upperbound && arr[index] - arr[index-1] == leftequdiff; index++);       *pleftsublen = index - leftsubindex;
}
}// 返回值为最长等差数列的长度， int* pll为输出参数， 为数列的起始索引（以0为基础）
int subequaldifference(int *arr, int left, int right, int* pll)
{
if (left > right)
return -1; if (left == right)
{
*pll = left;
return 1;
} if (left + 1 == right)
{
if (arr[left] <= arr[right])
{
*pll = left;
return 2;
}
else
return -1;
} int mid = (left + right) / 2, leftsublenidx = 0, rightsublenidx = 0, len = 0; int sublenl = subequaldifference(arr, left, mid, &leftsublenidx);
int sublenr = subequaldifference(arr, mid + 1, right, &rightsublenidx); if (sublenl > 0)
extendToRight(arr, right, leftsublenidx, &sublenl); if (sublenr > 0)
extendToLeft(arr, sublenl > 0 ?leftsublenidx:left, &rightsublenidx, &sublenr); if (sublenl >= sublenr)
{
*pll = leftsublenidx;
len = sublenl;
}
else
{
*pll = rightsublenidx;
len = sublenr;
} return len;
}void equal_difference()
{
int dataarray[] = {-1,  1,  3,  5,   7,  9,  9, 11, 13, 15, 
17,  10, 19, 21, 23, 25, 27, 29, 31, 33, 
35, 37}; int iNum = sizeof(dataarray)/sizeof(dataarray[0]); int longest = 0, len = 0; len = subequaldifference(dataarray, 0, iNum - 1, &longest);
}

Answer 30

/********************************************************************
purpose: 微软笔试题 求随机数构成的数组中找到长度大于=3的最长的等差数列
输出等差数列由小到大: 
如果没有符合条件的就输出
格式：
输入[1,3,0,5,-1,6]
输出[-1,1,3,5]
要求时间复杂度，空间复杂度尽量小 *********************************************************************/
#include <iostream>
#include <set>
#include <vector>using namespace std;// 归并排序
void Merge(int rOrg[], int rBuf[], int from, int mid, int to)
{
int i = from;
int j = mid + 1;
int k = from;
while (i <= mid && j <= to)
{
if (rOrg[i] <= rOrg[j])
rBuf[k++] = rOrg[i++];
else
rBuf[k++] = rOrg[j++];
}
if (i <= mid)
while (i <= mid)
rBuf[k++] = rOrg[i++];
else
while (j <= to)
rBuf[k++] = rOrg[j++];
while(k>from)
rOrg[--k] = rBuf[k];
}
// 归并排序
void MergeSort(int r[], int rBuf[], int from, int to)
{
if (from == to)
rBuf[from] = r[from];
else
{
int mid = (from + to) / 2;
MergeSort(r, rBuf, from, mid);
MergeSort(r, rBuf, mid + 1, to);
Merge(rBuf, r, from, mid, to);
}
}
// 二分查找
int BinarySearch(int *r, const int &item, int left, int right)
{
int middle;
while(left <= right)
{
middle = (left + right)/2;
if(r[middle] == item)
return middle;
else if(r[middle] < item)
left = middle + 1;
else
right = middle - 1;
}
return -1;
}// 求随机数构成的数组中找到长度大于=3的最长的等差数列
void MaxLenEQDistSubArray(int rOrg[], int len) {
if (rOrg == NULL || len < 3) {
return;
}
int *rBuf = new int[len]; // 用于归并排序
MergeSort(rOrg, rBuf, 0, len-1); int** steps = new int*[len];
int* stepP;
int i, j, k, jEnd, left, right=len-1,
curEndI, curDist, curLastItem, curLen=0,
maxEndI, maxDist, maxLastItem, maxLen=2; // 初始化 步数数组
for (i = 0; i < len; i++) {
steps[i] = new int[len-i];
stepP = steps[i];
for (int j = len-i-1; j >= 0; j-- ) {
stepP[j] = 0;
}
} // 开始查找最大等差子数组
for (i = 0; i < len; i++) {
jEnd = len - i;
stepP = steps[i];
for (j = i + 1; j < jEnd; j++) {
if (stepP[j-i]) {
continue;
}
stepP[j-i]=1;
curLastItem = rOrg[j];
curDist = rOrg[j]-rOrg[i];
left = j;
curLen = 2;
while ((k=BinarySearch(rOrg, curLastItem+curDist, left+1, right)) != -1) { //是否存在下一等差数
curLen++;
curLastItem += curDist;
steps[left][k-left] = 1;
left = k;
}
if (curLen > maxLen) {
maxLen = curLen;
maxLastItem = curLastItem;
maxDist = curDist;
}

}
} // 输出结果
if (maxLen >= 3) {
int start = maxLastItem - maxDist*(maxLen-1);
cout<<"max length:"<<maxLen<<endl;
cout<<"max sub array: ";
while(maxLen--)
{
cout<<start<<" ";
start += maxDist;
}
} else {
cout<<"no GT 3 length sub array"<<endl;
} delete[] rBuf;
delete[] steps;
}void Test_MaxLenEQDistSubArray()
{
//// test MergeSort
//const int LEN = 8;
//int rOrg[LEN]={10,3,5,1,9,34,54,565},rBuf[LEN];
//MergeSort(rOrg, rBuf, 0, LEN-1);
//for (int i = 0; i < LEN; i++)
// cout << " " << rOrg[i]; int rOrg[] = {1,3,0,5,-1,6};
MaxLenEQDistSubArray(rOrg, sizeof(rOrg)/sizeof(rOrg[0]));
}

Answer 31

我想我的可能差不多最快了，首先最坏的情况理论上讲每两个数都要减一次，如果比这个还要多，那算法肯定不是最好的，我的做到了这一点。思路主要见核心那部分代码
    // 开始查找最大等差子数组
    for (i = 0; i < len; i++) {
        jEnd = len - i;
        stepP = steps[i];
        for (j = i + 1; j < jEnd; j++) {
            if (stepP[j-i]) {
                continue;
            }
            stepP[j-i]=1;
            curLastItem = rOrg[j];
            curDist = rOrg[j]-rOrg[i];
            left = j;
            curLen = 2;
            while ((k=BinarySearch(rOrg, curLastItem+curDist, left+1, right)) != -1) { //是否存在下一等差数
                curLen++;
                curLastItem += curDist;
                steps[left][k-left] = 1;
                left = k;
            }
            if (curLen > maxLen) {
                maxLen = curLen;
                maxLastItem = curLastItem;
                maxDist = curDist;
            }
            
        }
    }

Answer 32

jEnd = len - i;
改成，jEnd = len-2;

Answer 33

改成，jEnd = len-1;
嘿嘿，先前本来想直接用index差，后来……

Answer 34

求的是长度至少为3的最大的等差子数组。
思路：
遍历indexI∈[0,n)
　　遍历indexJ∈[indexI,n-1)
　　　　若先前没求过indexI 的索引步长为 [indexJ-indexI-1]，则：
　　　　求以indexI indexJ为起始两个数组成的等差数列的最长项，求的过程中保存每一项到下一项的索引步长程序里还有错误，郁闷了，
stepP[j-i]=1; =》 stepP[j-i-1]=1;
steps[left][k-left] = 1; =》 steps[left][k-left-1] = 1;

Answer 35

再发一次核心代码
// 开始查找最大等差子数组
// i为等差第一项的位置 j为等差第二项位置
for (i = 0; i < len; i++) {
jEnd = len - 1; // 要求的等差数列最小长度为3，等差第二项最大为原数组倒数第二项
stepP = steps[i];
for (j = i + 1; j < jEnd; j++) {
if (stepP[j-i-1]) { // ① 此index步长j-i己被前面②计算过
continue;
}
//stepP[j-i-1]=1; // 可省略，因为不会再访问这个标志
curLastItem = rOrg[j];
curDist = rOrg[j]-rOrg[i]; // 本次等差
left = j;
curLen = 2;
while ((k=BinarySearch(rOrg, curLastItem+curDist, left+1, right)) != -1) { //是否存在下一等差数
curLen++;
curLastItem += curDist;
steps[left][k-left-1] = 1; // ② 记录 index为left位置 index步长k-left 的数组己被前面计算过
left = k;
}
if (curLen > maxLen) { // 记录最大等差数列信息
maxLen = curLen;
maxLastItem = curLastItem;
maxDist = curDist;
}

}
}

Answer 36

http://blog.csdn.net/wcyoot/archive/2011/05/22/6437382.aspx