从3 sum问题说起

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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数求和问题的解答了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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}。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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!