algorithm - 算法 - 找到数组中两个数字之和的最大数字

Question

描述：

给定一个由 n 个正整数组成的数组，找到使 C=A+B 的最大 C。A,B,C 都在给定的数组中。

例子：

1 1 1 4 5 5 6 6 10 9 C=10

1 3 6 C=-1，表示最大的C不存在

我正在寻找一种小于 O(n^3) 的算法，谁能给我一些指导？

Answer 1

对列表进行排序。从最大到最小迭代 C，从最小到 C 的值迭代 B。到目前为止，它是 O(n^2)。对于每个 (C, B) 对，计算 A，您只需要查找它是否在数组中。您可以对 O(n^2 log n) 的总时间使用二进制搜索。

Answer 2

O(n^2) 基于@valtron 的算法就足够了

Answer 3

更高效的解决方案：

1 1 1 4 5 5 6 6 9 10 10

• 对数组进行排序
• 保留 3 个指针 C、B 和 A。
• 将 C 保持在最后，将 A 保持在 0 索引，将 B 保持在第 1 索引。
• 使用指针 A 和 B遍历数组直到 C 并检查 A+B=C 是否存在。
  如果它存在，那么 C 就是你的答案。
• 否则，将 C 移回一个位置并再次遍历，将 A 保持在 0 并将 B 保持在第一个索引。

继续重复此操作，直到您获得总和或 C 在第一个索引处达到。

这是完整的解决方案：

int arr[] = new int[]{1,1,1,4,5,5,6,6,10,9};
Arrays.sort(arr);

        int n=arr.length;
        int a,b,c,sum,max=-1;

        for(c=n-1;(c>1)&& (max==-1);c--){       // loop through C
            for(a=0;(a<c-1)&&(max==-1);a++){    // loop through A
                for(b=a+1;b<c;b++){             // loop through B
                    sum=arr[a]+arr[b];
                    if(sum==arr[c]){
                         System.out.println("A: "+arr[a]+" B: "+arr[b]);
                        max=arr[c];
                        break;
                    }
                    if(sum>arr[c]){ // no need to go further
                        break;
                    }
                }
            }
        }

System.out.println(max);