数据结构与算法
双指针、回溯剪枝、图论与搜索
🎨 视觉封面LeetCode Contains Duplicate II
Problem
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
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
Python3
# 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
class Solution:
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
temp_dict = {}
for idx in range(len(nums)):
if nums[idx] in temp_dict:
if idx - temp_dict.get(nums[idx]) <= k:
return True
temp_dict[nums[idx]] = idx
return False
分析
用dict保存值对应的索引位，当发现相同的元素时，计算距离。如果满足题意，返回True即可，否则更新最新索引位，继续计算。
所有代码开源上传至 GitHub：yummy-code 仓库 · GESP 专题站：GESP WIKI
欢迎加入：C++ GESP/CSP 考级答疑群（688906745） 与 Java/Python交流群（982860385），点击可直接加群。
猜你想读 · 相关文章推荐
LeetCode Minimum Depth of Binary Tree
Problem Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest lea...
LeetCode Path Sum
Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For...
LeetCode Path Sum II
Problem Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum...
OneCoder (lihongzheshuai)
一个中年人的自留地，记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址：coderli.com