在一个升序排列的正整数集合中找出使C=A+B且A，B，C都在集合中，返回该C值。（不调用任何库方法）

Question

在一个升序排列的正整数集合中找出使C=A+B且A，B，C都在集合中，返回该C值。（不调用任何库方法）

Answer 1

void test(){
    int n = 14;
    unsigned int data[]={0,0,0,1,2,2,3,4,4,5,6,7,8,9};

    //start
    int c;
    for(c = 2;c<n;c++){
        int i= c;
        for(;data[i] == data[i+1];i++){}
        int a=0,b=0;

        for(;a <= i;a++){
            if(a == c) continue;
            unsigned int val = data[c] - data[a];
            b = a+1;
            if(b >i || data[b] > val)
                continue;
            for(;b <= i && data[b] <= val;b++)
                if(b !=c && data[b] == val)
                    printf("%d(%d) = %d(%d) + %d(%d)\n",data[c],c,data[a],a,data[b],b);
        }
    }
}

Answer 2

整体思路是个3层的循环：
按排序，A记为第1元素，B是第2元素，C是第3元素，
判断，如果C不是目标元素，则C继续后移为第4元素。。直至尾部

C循环一轮后，B移动到第3元素，C为第4元素，再次判断C并继续后移C直到尾部

B循环一轮后，A移到第2元素，B是第3元素，C是第4元素，重新迭代直到A到尾部，即完成所有判断

集合记为set，大概意思如下

auto a = set.begin            //这里a是首迭代器
auto b = a+1                    //b是a下一个元素
while (a<set.end){        //a从头到尾遍历
    while(b<set.end){      //b从头遍历，且保证c不越界
        auto c=b+1;             //c从b的下一个元素开始
        if(c=set.end) break;
        while (c<set.end){    
            if(*c>*b+*a) break;    //如果C过大，则后面的元素更大，不必继续比较
            if(*c=*b+*a) return *c;
            if(*c<*b+*a) c++;        //如果C过小，则继续比较后面的元素
        }
        b++
    }
    a++
}

Answer 3

我的思路，对于集合 S{i}, i<n, 且 c = a + b，做二重循环

1. a 循环 S{i}, 0 <= i < n
2. b 循环 S{j}, i <= j < n
3. 判断 a + b 是否在 S{k}, j <= k < n

为提高性能，做了些优化

1. a 上限为 S 中最大值的一半
2. 对于 b 循环，若 b + a > S 最大值，结束循环
3. 采用二分法查找元素

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 二分法，判断 c 是否存在于数组 numbers 的区间 (start, end) 内。
int is_in_range(int c, int* numbers, int start, int end)
{
    if (end == start)
        return numbers[start] == c;
    if (end == start + 1)
        return 0;
    int middle = (end + start) / 2;
    int m = numbers[middle];
    if (c == m)
        return middle;
    if (c < m)
        return is_in_range(c, numbers, start, middle);
    return is_in_range(c, numbers, middle, end);
}

// 打印出数组 numbers 中，所有 c = a + b 的组合。
void find_c(int* numbers, int count)
{
    int max = numbers[count - 1];
    int middle = (max + 1) / 2;
    for (int i = 0; i < count; i++) {
        int a = numbers[i];
        if (a > middle)
            break;
        for (int j = i; j < count; j++) {
            int b = numbers[j];
            if (a + b > max)
                break;
            if (a + b == numbers[j] || a + b == numbers[count - 1]
                || is_in_range(a + b, numbers, j, count - 1))
                printf("%3d + %3d = %3d\n", a, b, a + b);
        }
    }
}

int main(int argc, char** argv)
{
    assert(argc > 1);

    int count = argc - 1;
    int* numbers = (int*)malloc(sizeof(int) * count);
    assert(numbers);

    for (int i = 1; i < argc; i++) {
        numbers[i - 1] = atoi(argv[i]);
        assert(numbers[i - 1] > 0);
        if (i >= 2)
            assert(numbers[i - 1] >= numbers[i - 2]);
    }

    find_c(numbers, count);
}