219.Contains Duplicate II

August 16, 2016

219.Contains Duplicate II

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 difference between i and j is at most k.

判断重复元素系列的第二题,这次不仅要找到是否存在重复元素,而且要求两元素下标之差不大于k,这个题用hash_table就比较合适了,见代码:

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> hash_table;
        int i=0;
        for(i=0;i<nums.size();i++){
            if(hash_table.find(nums[i])!=hash_table.end()&&i-hash_table[nums[i]]<=k)
                return true;
            hash_table[nums[i]]=i;
        }
        return false;
    }
};
  • [ TODO Contains Duplicate III]

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017