面试题 16.21. 交换和-哈希表解法

面试题 16.21. 交换和-c语言

给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。

返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。

示例:

输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
输出: [1, 3]

示例:

输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
输出: []
解题代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

 #define size 100
struct hash{
 
 int val;
 struct hash *next;
};
void hash_add(int val,struct hash *h){
    struct hash *p=(struct hash*)malloc(sizeof(struct hash));
    p->val=val;
    p->next=h->next;
    h->next=p;
}
int find_hash(int val,struct hash *h){
    h=h->next;
    while(h){
        if(h->val==val){
            return 1;
        }
          h=h->next;
    }
    return 0;
}



int* findSwapValues(int* array1, int array1Size, int* array2, int array2Size, int* returnSize){
    struct hash *h=(struct hash *)malloc(sizeof(struct hash)*size);
    int i;
    int *a=(int *)malloc(sizeof(int)*2);
    for(i=0;i<size;i++){
        (h+i)->next=NULL;
    }
    int sum1=0,sum2=0;
     for(i=0;i<array1Size;i++){
       sum1=sum1+array1[i];
    }
     for(i=0;i<array2Size;i++){
         hash_add(array2[i],h+array2[i]%size);
       sum2=sum2+array2[i];
    }
    int di=sum1-sum2;
    if(abs(di)%2==1){

          *returnSize=0;
    return NULL;
    }
    else{
        di=di/2;
    }
    printf("%d ", di);
    if(di==0) return false;
    for(i=0;i<array1Size;i++){
        int r;
        if(di>0&&array1[i]-abs(di)>0){
          r=find_hash(array1[i]-di,h+(array1[i]-abs(di))%size);
        }
        else{
           r=find_hash(array1[i]-di,h+(array1[i]+abs(di))%size);
        }
    
      if(r==1){
          a[1]=array1[i]-di;
          a[0]=array1[i];
          * returnSize=2;
            return a;

      }
    
    }
    *returnSize=0;
    return NULL;




}