从3 sum问题说起

3sum问题就是3数求和问题，可以简单描述如下：给定数据集S找出数据集中的三个元素a,b,c，满足a+b+c=k。直接可能没什么思路，其实3数求和问题可以看成是下面这个问题的扩展：给定数据集S，找出所有数据对a,b，满足a+b=k。

其实对于原始问题的求解时间复杂度可以达到O(n)，如果数据集是已排好序的。分别在头部和尾部设置两个指针，求其和，如果大于K，则尾部的指针向头部移动，否则头部的指针向后移动。用C语言简单实现如下。

void find2sum(int dataSet[], int itemNum, int key)
{
    int left=0;
    int right = itemNum-1;

    while(left<right){
        if(dataSet[left]+dataSet[right] == key)
            printf("The pair (%d %d) bingo!", left, right);
        else if(dataSet[left]+dataSet[right] < key)
            left ++;
        else
            right --;
    }
}

对上面的方法进行扩展就可以得到3数求和问题的解答了。

void find3sum(int dataSet[], int itemNum, int key)
{
    int i, left, right;
    sort(dataSet);
    for(i=0; i<itemNum-2; i++){
        left    = i+1;
        right   = itemNum-1;
        while(left<right){
            if(sum(i, left, right) == key)
                printf("triplet %d %d %d bingo!\n", i, left, right);
            else if(sum(i, left, right) < key)
                left ++;
            else
                right ++;
        }
    }
}

如果文章从这儿就结束了，那也没有写的必要了。

前面求解两数求和问题的时候提到了数组是排好序的，利用这一特性我们可是可以大做文章了。例如：如何求解两个已排序数组的公共子序列？

首先说明下，公共子序列和公共子串是不同的。公共子串是连续的，而公共子序列则没有这一限制。比如{1，2，3，4，5，6｝的子序列可以是｛1，3，6｝。

我们不妨设置两个数组分别为A，B，长度分别为m，n。结合上文，很容易可以得到时间复杂度为O(m+n)的解法。分别设置两个指针指向两个数组，然后比较，将较小的指针往前移动即可。

另外说到排序好的数组，一个自然反应应该就是二分查找了。对于数组A中的每个元素，对数组B进行二分查找，时间复杂度为O(mlgn)。其实这个讨论是有必要的，当m<<n时，这种方法明显优于上面的。

其实个人觉得效率还可以更高，只要将上面两种方法结合起来，定性描述如下。第一种方法的思想，当找到A[i]=B[j]的时候，下一次对B进行二分查找的时候，只需要查找B[j+1, n-1]。

void commonSeq(int A[], int B[], int m, int n)
{
    int index_A, index_B, result;

    index_A = index_B = 0;
    while(index_A<m && index_B<n){
        result = bisearch(B, index_B, n, A[index_A]);
        if(-1 == result)    /*使没查找到时返回-1*/
            index_A ++;
        else{
            printf("%d\t", A[index_A]);
            index_A ++;
            index_B = result+1;
        }
    }
    printf("\n");
}

还有一些，以后再说吧！
see you!