1590. 使数组和能被 P 整除-哈希表法

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

示例 2：

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

示例 3：

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

示例 4：

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0
解题代码如下：

struct hash{
    int val;
    int index;
    struct hash *next;

};

void add_hash(struct hash * h,int val,int index){
    struct hash *p=(struct hash *)malloc(sizeof(struct hash ));
    p->val=val;
    p->index=index;
    p->next=h->next;
    h->next=p;
}
int  find(struct hash * h,int max_index){
    struct hash *p=h->next;
    int index=-1;
    while(p){
        if(p->index<max_index){
             index=fmax(index,p->index);

        }
       
        p=p->next;
    }
    return index;
}

int minSubarray(int* nums, int numsSize, int p){
    long long sum=0;
    int size=p+10;
    struct hash *h=(struct hash *)malloc(sizeof(struct hash )*size);
    
     for(int i=0;i<numsSize;i++){
        sum=sum+nums[i];
       
        (h+sum%p)->next=NULL;

    }
    sum=0;

     for(int i=numsSize-1;i>=0;i--){
        sum=sum+nums[i];
        (h+p-sum%p)->next=NULL;
          
    }
    sum=0;
   
    for(int i=0;i<numsSize;i++){
        sum=sum+nums[i];
       
        add_hash(h+sum%p,nums[i],i);

    }
printf("dfs");

   
   
    sum=0;
    int min=numsSize;

    for(int i=numsSize-1;i>=0;i--){
        sum=sum+nums[i];
        int index=find(h+p-sum%p,i);
        
          if(index!=-1){
               min=fmin(min,numsSize-index-(numsSize-i)-1);
          }      
    }

    
   if(min==numsSize){
       sum=0;
     for(int i=0;i<numsSize;i++){
        sum=sum+nums[i];
       if(sum%p==0){
           min=fmin(min,numsSize-i-1);
       }
    }

    sum=0;
    for(int i=numsSize-1;i>=0;i--){
        sum=sum+nums[i];
       if(sum%p==0){
           min=fmin(min,i);
       }
    }
    

   }

    
   if(min==numsSize){
       return -1;
   }
 
    return min;

}