[LeetCode]219. 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.

1
2
3
4
5
6
7
8
9
10
11
12
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

Solution

Analysis

给定一个数组以及一个整数k, 在数组中查找是否存在两个相等的数组nums[i]和nums[j],而且i和j之间的绝对值差小于等于k.

最简单的方法是使用一个hash表记录数值和下标之间的映射关系, 记录时在遍历数组时同步记录,不用单独出来一个步骤,和two sum问题类似. 当出现重复数字时,判断是否满足条件, 如果不满足,更新hash表元素的下标, 当遍历完数组之后,还没有出现满足条件的情况,返回false.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> tabel;
        
        for (int i=0; i< nums.size(); i++){
            if (tabel.find(nums[i]) != tabel.end()){// found
                if (i - tabel[nums[i]] < k+1)
                    return true;
            }
            // 简写了: 合并出现过的情况, 
            tabel[nums[i]] = i;// 出现过,但不符合条件,更新; 没出现,赋值
        }
        return false;
    }
};
您的支持就是我更新的最大动力!谢谢!