1862: 求两个集合交集（暴力，双指针）

解题思路:

暴力的时间复杂度是n^2，因为这道题的数据规模较小，也可以通过

代码实现如下：

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

int gg(const void* x,const void *y){
	return *(int *)x-*(int *)y;
}

int main ()
{
	int i,j,k=0;
	int l[100001]={0};
	//int s[100001]={0};
	int p[100001]={0};
	int n,m,x;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++){
		scanf("%d",&l[i]);
	} 
	for(i=0;i<m;i++){
		scanf("%d",&x);
		for(j=0;j<n;j++){
			if(x==l[j]){
				p[k++]=x;
				break;
			}
		}
	}
	qsort(p,k,sizeof(int),gg);
	for(i=0;i<k;i++){
		printf("%d ",p[i]);
	}
	return 0;
}

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

代码实现如下：

#include <stdio.h>
#include <stdlib.h>
 
int cmp_int(const void *a, const void *b) {
    return *(int *) a - *(int *) b;
}
 
int main() {
    // 输入
    int n, m;
    scanf("%d%d", &n, &m);
    int A[n];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &A[i]);
    }
    int B[m];
    for (int i = 0; i < m; ++i) {
        scanf("%d", &B[i]);
    }
 
    // 排序
    qsort(A, n, sizeof(A[0]), cmp_int);
    qsort(B, m, sizeof(B[0]), cmp_int);
 
    // 查找交集
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (A[i] == B[j]) {
            printf("%d ", A[i]);
            i++;
            j++;
        } else if (A[i] > B[j]) {
            j++;
        } else {
            i++;
        }
    }
 
    return 0;
}