【算法比赛】在一个整数数组中寻找符合A+B=C的组合，使C为最大。看哪位高手的算法最快

【算法比赛】在一个整数数组中寻找符合A+B=C的组合，使C为最大。看谁的算法最快。
刚才在C/C++版看到这个算法问题。。。就搬到这里大家一起玩玩。。。

C# code

private void button1_Click(object sender, EventArgs e) 
 { 
     #region 初始化数组 
     int[] array = new int[arrayLength]; 
     Random random = new Random(1000); // 固定随机种子，使大家测试数据一致 
     for (int i = 0; i  < array.Length; i++) 
         array[i] = random.Next(arrayLength * 10); 
     #endregion 初始化数组 
  
     int A, B, C; 
     long tickCount = Environment.TickCount; 
     Search(array, out A, out B, out C); 
     Console.WriteLine("计算结果：A={0} B={1} C={2}，耗时:{3}",  
         A, B, C, Environment.TickCount - tickCount); 
 } 
  
 public void Search(int[] array, out int A, out int B, out int C) 
 { 
     A = -1; 
     B = -1; 
     C = -1; 
     /* TODO : 自由发挥 */ 
 }

C# code

public void Search(int[] array, out int A, out int B, out int C)        {            A = -1;            B = -1;            C = -1;            int[] all = new int[arrayLength * 10];            for (int i = 0; i < array.Length; i++)                all[array[i]]++;            for (int j = all.Length-1; j > 0; j--)            {                if (all[j] == 0) continue;                int num = j;                int halfnum=num/2;                if (num % 2 == 0)                {                    if (all[halfnum] >= 2)                    {                        A = B = halfnum;                        C = j;                        return;                    }                }                for (int t = 1; t < halfnum; t++)                {                    if (all[t] > 0 && all[num - t] > 0)                    {                        A = t;                        B = num - t;                        C = num ;                        return;                    }                }            }
[解决办法]
C# code
static public void Search(int[] array, out int A, out int B, out int C){    A = -1;    B = -1;    C = -1;    if( array == null || array.Length < 3) return;    // O(n*log n)    Array.Sort<int>(array);    int maxNumber = array[ array.Length-1 ];    bool hasZero = (array[0] == 0);    unsafe    {        byte* masks = stackalloc byte[maxNumber+2];        //if not Microsoft's CLR, DO initialize the allocated stack!        //for (int i = 0; i < maxNumber + 2; i++) masks[i] = 0;        for(int i=0; i<array.Length; i++)        {            masks[ array[i] ]++;        }        // O(n*n)        for(int i=array.Length -1; i>=0; i--)        {            int sum = array[i];            // special case            if( hasZero && masks[sum] > 1 )            {                A = 0; B = sum; C = sum; return;            }            int halfSum = sum / 2;            for(int j = i-1; j>0 && array[j] >= halfSum; j--)            {                if (masks[sum - array[j]] > 0)                {                    A = sum - array[j]; B = array[j]; C = sum;                    if (A != B || masks[A] > 1) return;                    else { A = B = C = -1; }                }            }        }    }    // done} 
 
[解决办法]
Hot fixes to my code in 10楼, for correctness in some very rare cases
C# code
static public void Search(int[] array, out int A, out int B, out int C){    A = -1;    B = -1;    C = -1;    if (array == null || array.Length < 3) return;    // O(n*log n)    Array.Sort<int>(array);    int maxNumber = array[array.Length - 1];    bool hasZero = array[0] == 0;    unsafe    {        byte* masks = stackalloc byte[maxNumber + 2];        //if not Microsoft's CLR, DO initialize the allocated stack!        //for (int i = 0; i < maxNumber + 2; i++) masks[i] = 0;        //        // hotfix 1: to avoid overflow of byte value, though seldom occurs with random values        //        for (int i = 0; i < array.Length; i++)        {            //masks[array[i]]++;            if (masks[array[i]] >= 1) masks[array[i]] = 2;            else masks[array[i]] = 1;        }        // O(n*n)        for (int i = array.Length - 1; i > 1; i--)       // change i >= 0 to i > 1        {            int sum = array[i];            // special case            if (masks[sum] > 1 && hasZero)            {                A = 0; B = sum; C = sum; return;            }            int halfSum = sum / 2;            for (int j = i - 1; j > 0 && array[j] >= halfSum; j--)            {                //                // hotfix 2: to handle {1,0,0} case                //                if (masks[sum - array[j]] > 0)                {                    A = sum - array[j]; B = array[j]; C = sum;                    //if (A != B || masks[A] > 1) return;                    if (A < B || masks[A] > 1) return;                    else { A = B = C = -1; }                }            }        }    }    // done}
[解决办法]
C# code
static public void Search(int[] array, out int A, out int B, out int C){    A = -1;    B = -1;    C = -1;    if (array == null || array.Length < 3) return;    // O(n*log n)    Array.Sort<int>(array);    int maxNumber = array[array.Length - 1];    bool hasZero = array[0] == 0;    Dictionary<int, int> masks = new Dictionary<int, int>(1024);    for (int i = 0; i < array.Length; i++)    {        int number = array[i];        if (masks.ContainsKey(number)) masks[number] = 2;        else masks[number] = 1;    }    // O(n*n)    for (int i = array.Length - 1; i > 1; i--)    {        int sum = array[i];        // special case        if (masks[sum] > 1 && hasZero)        {            A = 0; B = sum; C = sum; return;        }        int halfSum = sum / 2;        for (int j = i - 1; j > 0 && array[j] >= halfSum; j--)        {            if ( masks.ContainsKey(sum - array[j]) )            {                A = sum - array[j]; B = array[j]; C = sum;                if (A < B || masks[A] > 1) return;                else { A = B = C = -1; }            }        }    }}
[解决办法]
C# code
public static void Search(int[] array, out int A, out int B, out int C){    A = -1;    B = -1;    C = -1;    Array.Sort(array);    for (int i = array.Length - 1; i > 1; i--)    {        C = array[i];        for (int j = i - 1; array[j] > C / 2; j--)        {            A = array[j];            B = C - A;            if (Array.IndexOf(array, B, 0, j) > 0)            {                return;            }        }    }}
[解决办法]
个人感觉不错
主要是array[j] > C / 2
我觉得节省了不少时间
[解决办法]
一个大数分解问题 
 

1.排序找到最大数i
2.如果i为素数，移除i，然后找另一个最大数
3.如果i为和数，将i分解成素数集合
4.然后对于这个素数集合进行排列

大体如此
[解决办法]
个人感觉不错  
主要是array[j] > C / 2  
我觉得节省了不少时间
[解决办法]
恩，有盗码的嫌疑，鉴定完毕。
【盗码】最新网络词汇，有些人不喜欢自己编写代码，然后出题让别人来回答
[解决办法]
恩，好像还可以排序以后，用折半算法弄
[解决办法]
C# code
        public void Search(int[] array, out int A, out int B, out int C)        {            A = -1;            B = -1;            C = -1;            int a;            Array.Sort(array);            int intLen=array.Length-1;            for(int i=intLen;i>=0;i--)            {                if (tryFind(array,array[i],out a))                {                    C = array[i];                    A = a;                    B = C - A;                    break;                }            }        }        private bool tryFind(int[] array,int p,out int A)        {            A = -1;            int intLen = array.Length-1;            for (int i = 0; i < intLen-1; i++)                if (Array.IndexOf(array,p-array[i],i+1)!=-1)                {                    A=array[i];                    return true;                }            return false;        }
[解决办法]
也来凑个热闹
C# code
        public static void Search(int[] arr, out int a, out int b, out int c)        {            a = b = c = -1;            int arrCount = arr.Length;            int cIndex = arrCount-1;            int bIndex = arrCount-2;            int aIndex = arrCount-3;            if(arrCount<3)                return;            Array.Sort(arr);//            fixed(int* pi = &arr[0]) //            {//                while(cIndex > 1) //                {//                    c = pi[cIndex--];//                    bIndex = cIndex-1;//                    while(bIndex > 0) //                    {//                        b = pi[bIndex--];//                        aIndex = bIndex-1;//                        while(aIndex > -1) //                        {//                            a = pi[aIndex--];//                            if(a+b == c)//                                break;//                        }//                        if(a+b == c)//                            break;//                    }//                    if(a+b == c) //                    {//                        Console.WriteLine("a={0}\tb={1}\tc={2}\t", a, b, c);//                        break;//                    }//                }//            }            //            while(cIndex > 1) {//                c = arr[cIndex--];//                bIndex = cIndex-1;//                while(bIndex > 0) {//                    b = arr[bIndex--];//                    aIndex = bIndex-1;//                    while(aIndex > -1) {//                        a = arr[aIndex--];//                        if(a+b == c)//                            break;//                    }//                    if(a+b == c)//                        break;//                }//                if(a+b == c) //                {//                    Console.WriteLine("a={0}\tb={1}\tc={2}\t", a, b, c);//                    break;//                }//            }            //            while(cIndex > 1)             {                c = arr[cIndex--];                bIndex = cIndex-1;                while(bIndex > 0)                 {                    b = arr[bIndex--];                    //aIndex = bIndex-1;                    a = c - b;                    cIndex = Array.BinarySearch(arr, 0, arrCount-bIndex, a);                    if(cIndex>-1)                    {                        c = arr[cIndex];                        return;                    }                }                if(a+b == c)                 {                    Console.WriteLine("a={0}\tb={1}\tc={2}\t", a, b, c);                    break;                }            }        } 
 
[解决办法]
输入：{ 1, 4, 2, 3 }
输出：1+2=3


为啥不是1+3=4
[解决办法]
除了 算A+B=C 我是想不出更好的算法(写了3个循环……，感觉自己写的比系统带的快……）
不过这里折半并不一定适用,要知道 水哥给出的可是随机数,排序后是有重复的

[解决办法]
?算?果：A=67303 B=2147408237 C=2147475540，耗?:20

为什么我的结果跟你们都不一样。。。。。。。。

C# code
private static void Search(int[] array, out int A, out int B, out int C)        {            A = -1;            B = -1;            C = -1;            /* TODO : 自由发挥 */            Array.Sort(array);            for (int i = arrayLength - 1; i >= 2; i--)            {                for (int j = i - 1; j >= 1; j--)                {                    if (Array.IndexOf(array, array[i] - array[j], 0, j - 1) != 0)                                        {                        C = array[i];                        B = array[j];                        A = array[i] - array[j];                        return;                    }                }            }        }
[解决办法]
C# code
private static void Search_juneapple(int[] array, out int A, out int B, out int C)        {            A = -1;            B = -1;            C = -1;            if (array == null)            {                Console.WriteLine("array is null!");                return;            }            if (array.Length < 3)            {                Console.WriteLine("array too few!");                return;            }            Array.Sort<int>(array);            //foreach(int i in array)            //    Console.WriteLine("{0}",i);            int i;            int j;            for (i = array.Length - 1; i > 1;i-- )            {                for (j = i - 1; j > 0 ; j--)                {                    if (Array.BinarySearch<int>(array, 0, j, array[i] - array[j]) >= 0)                    {                        A = array[j];                        C = array[i];                        B = C - A;                        return;                    }                }            }        }
[解决办法]
C# code
using System;using System.Collections.Generic;using System.Text;namespace TempTestA1{    class Class13    {        public const int arrayLength = 30000; // 数组的长度 30000        static void Main()        {            #region 初始化数组            int[] array = new int[arrayLength];            Random random = new Random(1000); // 固定随机种子，使大家测试数据一致            for (int i = 0; i < array.Length; i++)                array[i] = random.Next(); // <<<<<<<<random.Next(arrayLength * 10); ->> random.Next();            #endregion 初始化数组            int A, B, C;            long tickCount = Environment.TickCount;            Search(array, out A, out B, out C);            //Search(new int[] { 3,0,5,3,6,8,7,9,6,2}, out A, out B, out C);            Console.WriteLine("计算结果：A={0} B={1} C={2}，耗时:{3}",                A, B, C, Environment.TickCount - tickCount);        }        public unsafe static void Search(int[] array, out int A, out int B, out int C)        {            if (arrayLength < 3) return; // 3 at least            fixed (int* parray = &array[0])            {                // sort                int* plast = parray + arrayLength;                int* pmax = plast - 1;                int* pmin = parray;                int* pel, p;                int el = 0;                while(pmin < pmax)                {                    pel = pmin;                    el = *pel;                    p = pel;                    while(++p < plast)                    {                        if (*p < el)                        {                            pel = p;                            el = *pel;                        }                    }                    if (pmin != pel)                    {                        *pel = *pmin;                        *pmin = el;                    }                    pmin++;                }                // search                pmin = parray + 1; // element 1, large than it, element 2                int max, half;                int* pa, pb;                int va, vb, vamin;                while (pmax > pmin)                {                    max = *pmax;                    half = max / 2;                    pb = pmax - 1;                    vb = *pb;                    while (vb > half)                    {                        pa = pb - 1;                        va = *pa;                        vamin = max - vb - 1; // 9 - 5 - 1 = 3, 9 - 9 - 1 = -1                        while (va > vamin)                        {                            if (va + vb == max)                            {                                A = va; B = vb; C = max; return;                            }                            pa--;                            va = *pa;                        }                        pb--;                        vb = *pb;                    }                    pmax--;                }            }                        A = -1;            B = -1;            C = -1;        }    }} 
 
[解决办法]
C# code
public void h_w_kingSearch(int[] array, out int A, out int B, out int C)        {            A = -1;            B = -1;            C = -1;            Array.Sort<int>(array);            int midindex = 0;                        for (int i = array.Length - 1; i >= 0; i++)            {                C = array[i];                int midv = C / 2;                for (midindex=0; midindex < array.Length; midindex++)                    if (array[midindex] > midv)                        break;                int maxj = midindex - 1;                for (; midindex < array.Length; midindex++)                {                    if (array[midindex] == B) continue;                    B = array[midindex];                    A = C - B;                    for (int j = maxj; j > 0; j--)                    {                        if (array[j] == A) return;                        if (array[j] > A) maxj = j - 1;                        if (array[j] < A) break;                    }                }            }        }
[解决办法]
天啦，我写的排序方法没NET带的快，
在改一下：

C# code
 
  
     public unsafe static void Search2(int[] array, out int A, out int B, out int C) 
     { 
  
       if (arrayLength  < 3) return; // 3 at least 
       Array.Sort <int>(array); 
       fixed (int* parray = &array[0]) 
       { 
         // sort 
  
         int* plast = parray + arrayLength; 
         int* pmax = plast - 1; 
         int* pmin = parray; 
         // search 
  
         pmin = parray + 1; // element 1, large than it, element 2 
  
         int max, half; 
         int* pa, pb; 
         int va, vb, vamin; 
  
         while (pmax > pmin) 
         { 
           max = *pmax; 
           half = max / 2; 
           pb = pmax - 1; 
           vb = *pb; 
           while (vb > half) 
           { 
             pa = pb - 1; 
             va = *pa; 
             vamin = max - vb - 1; // 9 - 5 - 1 = 3, 9 - 9 - 1 = -1 
             while (va > vamin) 
             { 
               if (va + vb == max) 
               { 
                 A = va; B = vb; C = max; return; 
               } 
               pa--; 
               va = *pa; 
             } 
             pb--; 
             vb = *pb; 
           } 
           pmax--; 
         } 
       } 
  
  
       A = -1; 
       B = -1; 
       C = -1; 
     } 
 

[解决办法]
C# code 
 
public void Search(int[] array, out int A, out int B, out int C)        {            A = -1;            B = -1;            C = -1;            /* TODO : 自由发挥 */            Array.Sort<int>(array);            for (int i = array.Length - 1; i >= 0; i--)            {                C = array[i];                for (int j = 0; j < array.Length - 1; j++)                {                    A = array[j];                    int bIndex = Array.BinarySearch<int>(array, C - A);                    if (bIndex > -1)                    {                        B = array[bIndex];                        return;                    }                }            }        }
[解决办法]
探讨

34楼代码有严重的算法漏洞，  

public void Yatobiaf_Search(int[] array, out int A, out int B, out int C)  

C = array[i];  
int lastIndex;  
BinarySeach(array, i, C / 2, out lastIndex);  


用 C / 2 来确定最小索引是不科学的，除非数组中没重负的值。  

用他的函数测试 Yatobiaf_Search(new int[] { 2,7,9,9,9,9,9,9,9,9,9,9,9,9,9}, out A, out B, out C);  

结果：  

计算结果：A=-1 B=-1 C=-1，耗时:…

[解决办法]
更正
C# code
public void h_w_kingSearch(int[] array, out int A, out int B, out int C)        {            A = -1;            B = -1;            C = -1;            Array.Sort<int>(array);            int midindex = 0;            int bakindex = array.Length - 2;            for (int i = array.Length - 1; i >= 0; i--)            {                if (array[i] == C) continue;                C = array[i];                int midv = C / 2;                for (midindex = bakindex; midindex >= 0; midindex--)                    if (array[midindex] < midv)                    {                        bakindex = midindex;                        break;                    }                midindex++;                int maxj = midindex-1 ;                for (; midindex < array.Length; midindex++)                {                    if (array[midindex] == B) continue;                    B = array[midindex];                    A = C - B;                    for (int j = maxj; j > 0; j--)                    {                        if (array[j] == A) return;                        if (array[j] > A) maxj = j - 1;                        if (array[j] < A) break;                    }                }            }        }
[解决办法]
目前朋友们贴的大致都是

C# code
Sort();for(){   for(){       Lookfor( A );   }}
[解决办法]
挑战 1.2亿不重复数据，内存消耗490M,基本上是数组所占据的内存

C# code
using System;using System.Collections.Generic;using System.Text;namespace TempTestA1{    class Class13    {        public const int arrayLength = 123456789; // 数组的长度 30000        static void Main()        {            #region 初始化数组            int[] array = new int[arrayLength];            //Random random = new Random(1000); // 固定随机种子，使大家测试数据一致            //for (int i = 0; i < array.Length; i++)            //    array[i] = new Random(i).Next(i * i); // <<<<<<<<random.Next(arrayLength * 10); ->> random.Next();            for (int i = 0; i < array.Length; i++)                array[i] = i * 3; // <<<<<<<<random.Next(arrayLength * 10); ->> random.Next();            #endregion 初始化数组            int A, B, C;            long tickCount = Environment.TickCount;            Search2(array, out A, out B, out C);            //gomoku_Search(array, out A, out B, out C);            //gomoku_Search(new int[] { 2, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }, out A, out B, out C);            Console.WriteLine("计算结果：A={0} B={1} C={2}，耗时:{3}",                A, B, C, Environment.TickCount - tickCount);        }        public unsafe static void Search2(int[] array, out int A, out int B, out int C)        {            if (arrayLength < 3) return; // 3 at least            Array.Sort<int>(array);            fixed (int* parray = &array[0])            {                // sort                int* plast = parray + arrayLength;                int* pmax = plast - 1;                int* pmin = parray;                // search                pmin = parray + 1; // element 1, large than it, element 2                int max, half;                int* pa, pb;                int va, vb, vamin;                while (pmax > pmin)                {                    max = *pmax;                    half = max / 2;                    pb = pmax - 1;                    vb = *pb;                    while (vb > half)                    {                        pa = pb - 1;                        va = *pa;                        vamin = max - vb - 1; // 9 - 5 - 1 = 3, 9 - 9 - 1 = -1                        while (va > vamin)                        {                            if (va + vb == max)                            {                                A = va; B = vb; C = max; return;                            }                            pa--;                            va = *pa;                        }                        pb--;                        vb = *pb;                    }                    pmax--;                }            }            A = -1;            B = -1;            C = -1;        }            }} 
 
[解决办法]
探讨

引用:
34楼代码有严重的算法漏洞，  

用 C / 2 来确定最小索引是不科学的，除非数组中没重负的值。  
 

这个很科学！两个小于C / 2的数相加不可能等于C的！关键是，咱们的算法复杂度都是O(n^2log(n))的，有没有可能降低算法复杂度？

[解决办法]
探讨

不知道array的排序速度是怎么样？ 
如果有比这个更好的排序算法，那么速度还是可以再快点的 

用c#其实就谈不上什么很厉害的算法了。。。用c写或许会考验哈大家。。。个人觉得

[解决办法]
探讨

不知道array的排序速度是怎么样？ 
如果有比这个更好的排序算法，那么速度还是可以再快点的 

用c#其实就谈不上什么很厉害的算法了。。。用c写或许会考验哈大家。。。个人觉得

[解决办法]
探讨

目前朋友们贴的大致都是 


C# code
Sort();
for(){
   for(){
       Lookfor( A );
   }
}




朋友们的Lookfor( A )有这么些方法，以及它们的复杂度： 


C# codeArray.IndexOf()                 O(n)
Array.BinarySearch()            O(log n)
Diciontary.Contains()           O(1)



所以，总体时间复杂度为O(n*n*n), O(n*n*log n), 和O(n*n) 
但是，Dictionary，或叫HashTable，有额外的的空间…

[解决办法]
O(n*n)的时间内做到比较简单
whu的oj上可以AC

先排序 从最后一个元素开始找
问题转化为在一个有序的数组上 查找两个数的和等于已知值

C/C++ code
#include <stdio.h>#include <stdlib.h>#include <memory.h>#define MAX 10005int cmp(const void * p,const void* q){    return (*(int*)p>*(int*)q)-(*(int*)q>*(int*)p);}int main(){    int t,i,n,a,b;    int num[MAX];    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        memset(num,0,sizeof(num));        for(i=0;i<n;i++)            scanf("%d",num+i);        qsort(num,n,sizeof(int),cmp);        for(i=n-1;i>=2;i--)        {            a = 0; b = i-1;            while(1)            {                if(num[a]+num[b]==num[i]||a==b)                    break;                if(num[a]+num[b]>num[i])                    b--;                else                    a++;            }            if(a!=b)                break;        }        if(i>=2)            printf("%d\n",num[i]);        else            printf("-1\n");    }    return 0;}