题目;
法一 解题思路:
|num[i] - num[j]| = k 可以理解为 num[j] = num[i] + k 和 num[j] = num[i] - k 两种情况。
int countKDifference(int* nums, int numsSize, int k) {
int ans = 0;
int hash[101];
memset(hash, 0, sizeof(hash));
for (int i = 0; i < numsSize; i++) {
int x = nums[i] + k;
if (x >= 1 && x <= 100) ans += hash[x];
x = nums[i] - k;
if (x >= 1 && x <= 100) ans += hash[x];
hash[ nums[i] ]++;
}
return ans;
}
法二 动态分配
typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashEntry;
int countKDifference(int* nums, int numsSize, int k){
int ans = 0;
HashEntry * cnt = NULL;
for (int j = 0; j < numsSize; ++j) {
HashEntry * pEntry = NULL;
int curr = nums[j] - k;
HASH_FIND(hh, cnt, &curr, sizeof(int),pEntry);
if (NULL != pEntry) {
ans += pEntry->val;
}
curr = nums[j] + k;
HASH_FIND(hh, cnt, &curr, sizeof(int), pEntry);
if (NULL != pEntry) {
ans += pEntry->val;
}
HASH_FIND(hh, cnt, &nums[j], sizeof(int), pEntry);
if (NULL == pEntry) {
pEntry = (HashEntry *)malloc(sizeof(HashEntry));
pEntry->key = nums[j];
pEntry->val = 1;
HASH_ADD(hh, cnt, key, sizeof(int), pEntry);
} else {
++pEntry->val;
}
}
HashEntry * curr = NULL, * next = NULL;
HASH_ITER(hh, cnt, curr, next) {
HASH_DEL(cnt, curr);
}
return ans;
}
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 【C语言刷力扣】2006.差的绝对值为K的数对数目
发表评论 取消回复