存在重复元素 II

题目描述

给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，满足 nums[i] == nums[j] 且 abs(i - j) <= k。

如果存在，输出 true；否则输出 false。

输入格式

第一行输入一个整数 n，表示数组长度。

第二行输入 n 个整数，表示数组 nums。

第三行输入一个整数 k。

输出格式

如果存在满足条件的两个索引，输出 true；否则输出 false。

数据范围

1 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9

0 <= k <= 10^5

样例 1

输入

4
1 2 3 1
3

输出

true

样例 2

输入

4
1 0 1 1
1

输出

true

样例 3

输入

6
1 2 3 1 2 3
2

输出

false