大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个整数数组和一个整数k，判断数组中是否存在连个不同的索引，返回两个索引对应的数组的值相同是否存在。”
2、题目描述
给你一个整数数组 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
二、解题
1、思路分析
本题要要判断在整数数组中是否有满足条件 nums[i] == nums[j] 且 abs(i - j) <= k 的数。
遍历数组nums，不断的判断下标 j < i 使得 nums[i] == nums[j]，且当i-j≤k时，就找到了符合题意的i和j。
如果要满足题意i-j≤k，那么在下标i之前存在于nums[i]相等的元素，应该先找到最大的下标j，判断i-j≤k是否成立。
用哈希表记录每个元素的最大下标，遍历数组：
- 如果哈希表中存在和nums[i]相等的元素且该元素在哈希表中记录的下标j满足i-j≤k，则返回true
- 将nums[i]和下标i存入哈希表，此时i是nums[i]的最大下标
重复以上操作，当遍历结束没有遇到两个相等元素的下标差的绝对值不超过k，则返回false。
2、代码实现
代码参考：
class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int nr = grid.length; int nc = grid[0].length; int num_islands = 0; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; grid[r][c] = '0'; Queue<Integer> neighbors = new LinkedList<>(); neighbors.add(r * nc + c); while (!neighbors.isEmpty()) { int id = neighbors.remove(); int row = id / nc; int col = id % nc; if (row - 1 >= 0 && grid[row-1][col] == '1') { neighbors.add((row-1) * nc + col); grid[row-1][col] = '0'; } if (row + 1 < nr && grid[row+1][col] == '1') { neighbors.add((row+1) * nc + col); grid[row+1][col] = '0'; } if (col - 1 >= 0 && grid[row][col-1] == '1') { neighbors.add(row * nc + col-1); grid[row][col-1] = '0'; } if (col + 1 < nc && grid[row][col+1] == '1') { neighbors.add(row * nc + col+1); grid[row][col+1] = '0'; } } } } } return num_islands; } }
3、时间复杂度
时间复杂度：O(n)
其中n是数组nums的长度，需要遍历数组一次，对于每个元素，哈希表的操作时间都是O(n)。
空间复杂度：O(n)
其中n是数组nums的长度，需要用哈希表来记录每个元素的最大下标，哈希表中的元素个数不会超过n。
三、总结
维护一个哈希表。
哈希表里面时钟最多包含k个元素，出现重复值则说明在k的区间内存在重复元素。
每次遍历一个元素则将钙元素加入哈希表汇总，如果哈希表的大小大于k，则移除最前面的数字。
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)