leetcode 219. 存在重复元素 II

给你一个整数数组

nums

和一个整数

k

，判断数组中是否存在两个 不同的索引* *

i

和* *

j

，满足

nums[i] == nums[j]

且

abs(i - j) <= k

。如果存在，返回

true

；否则，返回

false

。

示例 1：

**输入：**nums = [1,2,3,1], k= 3
**输出：**true

示例 2：

**输入：**nums = [1,0,1,1], k=1
**输出：**true

示例 3：

**输入：**nums = [1,2,3,1,2,3], k=2
**输出：**false

• 1 <= nums.length <= 10e5
• -109 <= nums[i] <= 10e9
• 0 <= k <= 10e5

分析：其实这道题最直接的还是哈希。因为总数据量只有10的5次方，但是毕竟是排序这节的内容，所以还使用排序做了。注意排序除了值的大小，还有下标也要排序。

typedef struct num{
    int value,index;
}num;

int cmp(const void *a,const void *b)
{
    num *aa=(num*)a;
    num *bb=(num*)b;
    if(aa->value!=bb->value)return aa->value-bb->value;
    return aa->index-bb->index;
}
bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
    //if(k==1)return 0;
    num ans[numsSize+5];
    for(int i=0;i<numsSize;++i)
        ans[i].value=nums[i],ans[i].index=i;
    
    qsort(ans,numsSize,sizeof(ans[0]),cmp);
    int value=ans[0].value,index=ans[0].index;
    for(int i=1;i<numsSize;++i)
    {
        if(ans[i].value==value)
        {
            if(ans[i].index-index<=k)return 1;
            else index=ans[i].index;
        }
        else value=ans[i].value,index=ans[i].index;
    }
    return 0;
}