[经典面试题][百度]在由N个正整数的集合S中，找出最大元素C，满足C=A + B - Yoona - 博客频道 - CSDN.NET
2，让C指向集合最后一个元素（最大元素）
3，让i指向S中第一个元素，让j指向C的前一个元素
4，如果，A[i]+A[j]==C则return C;
5，如果if(A[i]+A[j]<C)则i++;
6，如果if(A[i]+A[j]>C)则j--;
7，直道i>=j依然没有找到符合条件的元素，则C在S中向前移动一位，跳至步骤3
在由N个正整数的集合S中，找出最大元素C，满足C=A + B 其中A,B都是集合S中元素，请给出算法描述，代码与时间复杂度分析。
【分析】
1，对集合S进行排序（快排），从小到大排序2，让C指向集合最后一个元素（最大元素）
3，让i指向S中第一个元素，让j指向C的前一个元素
4，如果，A[i]+A[j]==C则return C;
5，如果if(A[i]+A[j]<C)则i++;
6，如果if(A[i]+A[j]>C)则j--;
7，直道i>=j依然没有找到符合条件的元素，则C在S中向前移动一位，跳至步骤3
int FindSum(int A[],int n){
// 排序
sort(A,A+n);
int left,right,sum;
// i = C
for(int i = n - 1;i >= 2;--i){
left = 0,right = i - 1;
// 判断是否有A + B = i
while(left < right){
sum = A[left] + A[right];
if(sum == A[i]){
return A[i];
}//if
else if(sum > A[i]){
--right;
}
else{
++left;
}
}//while
}//for
return -1;
}
Read full article from [经典面试题][百度]在由N个正整数的集合S中，找出最大元素C，满足C=A + B - Yoona - 博客频道 - CSDN.NET