LEET code -- Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

1 2 3 4 5 6 7 8 9

bool containsNearbyDuplicate(int* nums, int numsSize, int k) { if(!nums )return false; for(int i=0;i<numsSize;i++){ for(int j=i+1;j<numsSize && j<=i+k;j++){ if(nums[i]==nums[j])return true; } } return false; }

----------------------
這題唯一解:
用hash  但是C 沒有  所以要自己寫一個

下面是錯的
因為13 行 不是 *hashHead ，不能是指標
因為HASH陣列 裡面存的是struct Node型態  不是指標
如果要變成指標來處理
那必須HSH為double pointer，讓每個array值都是pointer 的型態

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

struct Node{ int val; int index; struct Node* next; }; bool containsNearbyDuplicate(int* nums, int numsSize, int k) { if(!nums)return false; struct Node *HASH =calloc(numsSize,sizeof(struct Node)); for(int i=0;i<numsSize;i++){ int hashIndex=nums[i]%numsSize; struct Node *hashHead=HASH[hashIndex]; if(hashHead==NULL){ hashHead->val=nums[i]; hashHead->index=i; hashHead->next=NULL; }else{ while(true){ if(hashHead->val==nums[i] && hashHead->index + k>i)return true else if (hashHead->val==nums[i] && hashHead->index + k<i){ hashHead->index=i; break; } // if(hashHead->next==NULL){ //new hash value struct Node *temp=malloc(sizeof(struct Node)); temp->val=nums[i]; temp->index=i; temp->next=NULL; hashHead->next=temp; break; }else{ hashHead=hashHead->next; } } } } }

下面是可以跑的
要注意的是我原本在16~20行是寫

       hashHead = malloc(sizeof(struct Node)); 

            hashHead->val=nums[i];
            hashHead->index=i;
            hashHead->next=NULL;
但是不行   因為HASH[hashIndex] 裡面是空的   所以沒有給一個實體的struct Node記憶體位置
因此用hashHead = malloc(sizeof(struct Node));  是不行的  他是替 hashHead 這個變數下 新增一個，不是在HASH[hashIndex]的這個記憶體位置新增
HASH[hashIndex]: 0x13545 -->裡面內容NULL
hashHead :0x13577-->裡面NULL
alloc的是給內容  所以會造成失敗


PS:  calloc會初始化新增加的記憶體內容(都設為0)  比malloc好用

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

struct Node{ int val; int index; struct Node* next; }; bool containsNearbyDuplicate(int* nums, int numsSize, int k) { if(!nums || numsSize<=0)return false; struct Node **HASH =calloc(numsSize,sizeof(struct Node*)); for(int i=0;i<numsSize;i++){ int hashIndex=abs(nums[i])%numsSize; struct Node *hashHead=HASH[hashIndex]; //if(hashHead==NULL)printf("%d %d %d",nums[i],i); if(hashHead==NULL){ HASH[hashIndex] = malloc(sizeof(struct Node)); printf("%d %d ",nums[i],i); HASH[hashIndex]->val=nums[i]; HASH[hashIndex]->index=i; HASH[hashIndex]->next=NULL; }else{ while(true){ if(hashHead->val==nums[i] && (hashHead->index + k)>=i){ return true; printf("if %d %d ",nums[i],i); } else if (hashHead->val==nums[i] && hashHead->index + k<i){ hashHead->index=i; printf("else %d %d ",nums[i],i); break; } // if(hashHead->next==NULL){ //new hash value struct Node *temp=malloc(sizeof(struct Node)); temp->val=nums[i]; temp->index=i; temp->next=NULL; hashHead->next=temp; break; }else{ hashHead=hashHead->next; } } } } return false; }

後來想想  根本不用double pointer
因為可以用陣列 (第8行)
裡面只負責儲存pointer的值就好   這樣就好了

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

struct Node{ int val; int index; struct Node* next; }; bool containsNearbyDuplicate(int* nums, int numsSize, int k) { if(!nums || numsSize<=0)return false; struct Node *HASH =calloc(numsSize,sizeof(struct Node)); for(int i=0;i<numsSize;i++){ int hashIndex=abs(nums[i])%numsSize; //struct Node hashHead=HASH[hashIndex]; //if(hashHead==NULL)printf("%d %d %d",nums[i],i); if(HASH[hashIndex].next==NULL){ struct Node *temp=malloc(sizeof(struct Node)); temp->val=nums[i]; temp->index=i; temp->next=NULL; HASH[hashIndex].next=temp; }else{ struct Node *hashHead=HASH[hashIndex].next; while(true){ if(hashHead->val==nums[i] && (hashHead->index + k)>=i){ return true; printf("if %d %d ",nums[i],i); } else if (hashHead->val==nums[i] && hashHead->index + k<i){ hashHead->index=i; printf("else %d %d ",nums[i],i); break; } // if(hashHead->next==NULL){ //new hash value struct Node *temp=malloc(sizeof(struct Node)); temp->val=nums[i]; temp->index=i; temp->next=NULL; hashHead->next=temp; break; }else{ hashHead=hashHead->next; } } } } return false; }

--------------------
C++

1 2 3 4 5 6 7 8

bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map<int,int> map; for(int i = 0; i < nums.size(); i++){ if(map.count(nums[i]) && (i - map[nums[i]] <= k)) return true; map[nums[i]] = i; } return false; }