[349. 两个数组的交集]（C语言）（两种解法：双指针+排序，哈希）

/*法一*/
/*思路：排序+双指针*/


// int cmp(const void* e1, const void* e2)
// {
//     return *(int*)e1 - *(int*)e2;
// }

// int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
// {
//     int book[1005] = { 0 };
//     //要有一个标记的数组，防止数组中出现重复的数

//     qsort(nums1, nums1Size, sizeof(nums1[0]), cmp);
//     qsort(nums2, nums2Size, sizeof(nums2[0]), cmp);

//     int a = nums1Size < nums2Size ? nums1Size : nums2Size;
//     int* c = (int*)malloc(a * sizeof(nums1[0]));

//     int i = 0, j = 0, h = 0;
//     //i:nums1的下标 j:nums2的下标   h:c的下标
//     while (i < nums1Size && j < nums2Size)
//     {
//         if(nums1[i] == nums2[j])
//         {
//             if (book[nums1[i]] == 0)
//             {
//                 book[nums1[i]] = 1;
//                 c[h] = nums1[i];
//                 h++;
//             }
//             i++;
//             j++;
//         }
//         else if (nums1[i] > nums2[j])
//         {
//             j++;
//         }
//         else
//         {
//             i++;
//         }
//     }
  
//     *returnSize = h;
//     int* b = (int*)malloc(h * sizeof(nums1[0]));
//     for (int i = 0; i < h; i++)
//     {
//         b[i] = c[i];
//     }

//     return b;
// }

/*法二：哈希表*/
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
    int h=0;
    int hash[1001]={0};
    int i=0;
    int max=nums1Size<nums2Size?nums1Size:nums2Size;
    

    for(i=0;i<nums1Size;i++)
    {
        hash[nums1[i]]=1;
    }

    int j=0;
    int* ans=(int*)calloc(max,sizeof(nums1[0]));

    for(i=0;i<nums2Size;i++)
    {
        if(hash[nums2[i]]==1)
            {
                ans[j++]=nums2[i];
                hash[nums2[i]]=0;
                /*!!!!!!!记得置为0，否则最后ans中的数量可能大于max，因为可能有很多个重复出现的元素反复放入ans!!!!!!!!!*/
            }
    }

    *returnSize=j;
    return ans;
}