题目地址
https://leetcode.com/problems/contains-duplicate-ii/description/
题目描述
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
思路
由于题目没有对空间复杂度有求,用一个hashmap 存储已经访问过的数字即可,
每次访问都会看hashmap中是否有这个元素,有的话拿出索引进行比对,是否满足条件(相隔不大于k),如果满足返回true即可。
关键点解析
无
代码
- 语言支持:JS,Python,C++
Javascript Code:
/* * @lc app=leetcode id=219 lang=javascript * * [219] Contains Duplicate II * * https://leetcode.com/problems/contains-duplicate-ii/description/ * * algorithms * Easy (34.75%) * Total Accepted: 187.3K * Total Submissions: 537.5K * Testcase Example: '[1,2,3,1]\n3' * * Given an array of integers and an integer k, find out whether there are two * distinct indices i and j in the array such that nums[i] = nums[j] and the * absolute difference between i and j is at most k. * * * Example 1: * * * Input: nums = [1,2,3,1], k = 3 * Output: true * * * * Example 2: * * * Input: nums = [1,0,1,1], k = 1 * Output: true * * * * Example 3: * * * Input: nums = [1,2,3,1,2,3], k = 2 * Output: false * * * * * */ /** * @param {number[]} nums * @param {number} k * @return {boolean} */ var containsNearbyDuplicate = function(nums, k) { const visited = {}; for(let i = 0; i < nums.length; i++) { const num = nums[i]; if (visited[num] !== undefined && i - visited[num] <= k) { return true; } visited[num] = i; } return false };
Python Code:
class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: d = {} for index, num in enumerate(nums): if num in d and index - d[num] <= k: return True d[num] = index return False
C++ Code:
class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { auto m = unordered_map<int, int>(); for (int i = 0; i < nums.size(); ++i) { auto iter = m.find(nums[i]); if (iter != m.end()) { if (i - m[nums[i]] <= k) { return true; } } m[nums[i]] = i; } return false; } };LeetCode题解45.跳跃游戏 II
给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数…
LeetCode题解140. 单词拆分 II批注: 由于"可以重复使用字典中的单词", 因此稍微难一点定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明:分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1:输入:s = "catsanddog"wordDict = […
LeetCode题解142. 环形链表 II为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。说明:不允许修改给定的链表。 示例 1:输入:head = [3,2,0,-4], pos = 1输出:tail connects to node index 1解释:链表中有一个环,其尾部连接到第二个节点。示例 2…
LeetCode题解213. 打家劫舍 II你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。示例 1:输入: [2,3…
LeetCode题解212.word-search-ii题目地址(212. 单词搜索 II) https://leetcode-cn.com/problems/word-search-ii/description/ 题目描述 给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平…