数组模拟哈希表解决
使用y老师的模拟哈希表思路,利用数组模拟,涉及到映射,我用h数组和mp数组表示一对映射。
x
值由find(nums[i])
产生,这样h[x]
和mp[x]
成为一对映射,x作为中间人。
本地运行版本
思路:当查找到nums[i]时,查看target-nums[i]值是否在i之前出现过?如果没有出现,则把nums[i]和i作为一对映射分别存放到fi=find(nums[i])对应的下标内,h[fi]=nums[i]和mp[fi]=i。如果找到了,则ft=find(target-nums[i])对应的下标,之前曾经存过,则输出mp[ft](以前存的下标),i(当前下标)。
#include <cstdio>
#include <cstring>
using namespace std;
const int N=2e5+3,null=0x3f3f3f3f;
int h[N],nums[N],mp[N];
int find(int x){
int t=(x%N+N)%N;
while(h[t]!=null && h[t]!=x){
t++;
if(t==N) t=0;
}
return t;
}
int main(){
memset(h,0x3f,sizeof h);
int n,target;
scanf("%d%d",&n,&target);
for(int i=0;i<n;i++) scanf("%d",&nums[i]);
for(int i=0;i<n;i++){
int t=target-nums[i];
int ft=find(t);
int fi=find(nums[i]);
if(h[ft]!=null){
printf("%d,%d\n",mp[ft],i);
break;
}
else{
h[fi]=nums[i];
mp[fi]=i;
}
}
return 0;
}
力扣版本
class Solution {
public:
const static int N=2e5+3,null=0x3f3f3f3f;
int h[N],nums[N],mp[N];
int find(int x){
int k=(x%N+N)%N;
while(h[k]!=null && h[k]!=x){
k++;
if(k==N) k=0;
}
return k;
}
vector<int> twoSum(vector<int>& nums, int target) {
memset(h,0x3f,sizeof h);
int ft,fi,i,t;
for(i=0;i<nums.size();i++){
t=target-nums[i];
ft=find(t);
fi=find(nums[i]);
if(h[ft]!=null){
return {mp[ft],i};
}
else{
h[fi]=nums[i];
mp[fi]=i;
}
}
return {mp[ft],i};
}
};