454.四数相加II

这题运用了分组+哈希,四个数组,每个出一个数,加起来要为0,要循环四次太慢了,我们分成两组,每组用一个二次循环,第一组将其值的负数存入哈希表并且计数防止重复,第二组在哈希表里查找,找到了count+=tmp->count;

struct hashTable{
    int key;
    int count;
    UT_hash_handle hh;
};

struct hashTable* set=NULL;

void clearHashTable(){
    struct hashTable *current, *tmp;
    HASH_ITER(hh, set, current, tmp) {
        HASH_DEL(set, current);
        free(current);
    }
}

int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size) {
    clearHashTable();
    for(int i=0;i<nums1Size;i++){
        for(int j=0;j<nums2Size;j++){
            struct hashTable* tmp;
            int ikey=(-(nums1[i]+nums2[j]));
            HASH_FIND_INT(set,&ikey,tmp);
            if(tmp==NULL){
                tmp=malloc(sizeof(struct hashTable));
                tmp->key=ikey;
                tmp->count=1;
                HASH_ADD_INT(set,key,tmp);
            }
            else{
                tmp->count++;
            }
        }
    }
    int count=0;
    for(int i=0;i<nums3Size;i++){
        for(int j=0;j<nums4Size;j++){
            struct hashTable* tmp;
            int ikey=nums3[i]+nums4[j];
            HASH_FIND_INT(set,&ikey,tmp);
            if(tmp!=NULL){
                count+=tmp->count;
            }
        }
    }
    return count;
}