程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Contains Duplicate II

leetcode筆記:Contains Duplicate II

編輯:關於C++

一. 題目描述

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,當且僅當存在兩個不同的下標ij,滿足:nums[i] = nums[j],且| i - j | <= k時返回true,反之返回false

此題在前面一題Contains Duplicate的基礎上,要求兩個重復元素的下標相差不超過k。與上題的解法類似,令map中元素的值為key,元素下標為value,遍歷數組。當找到重復元素時,判斷兩個元素的下標差是否小於等於k。若大於k,更新已在map中元素對應的value,即下標的值。

三. 示例代碼

class Solution {
public:
    bool containsNearbyDuplicate(vector& nums, int k) {
        if (nums.size() < 2 || k < 1) return false;
        unordered_map numsMap;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (numsMap.count(nums[i]) == true)
            {
                if (i - numsMap[nums[i]] <= k)
                    return true;
                else numsMap[nums[i]] = i;
            }
            numsMap.insert(pair(nums[i], i));
        }
        return false;
    }
};

四. 小結

該題目使用unordered_map比map效率高。後續題目有:Contains Duplicate III。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved