leetcode 219 Contains Duplicate II

Scott 發布于2019-08-15 13:54 / 2703人閱讀

摘要：但上面這個想法并不是最簡單的，如果我們對任何索引大于的元素進行遍歷的時候，同時刪除中和當前元素的位置差已經超過的對應元素。這樣就可以減少后序查找的時間。

題目詳情

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.

這道題目的意思是：輸入一個整數數組和一個整數k，如果數組中存在相等的兩個數，而且他們的位置差不超過k，那么返回true，否則返回false

思路

這道題比較容易想到的想法就是用hashmap來存儲不同值的元素的值（key）和位置信息（value）。然后在每次遍歷的時候進行比較。

但上面這個想法并不是最簡單的，如果我們對任何索引大于k的元素進行遍歷的時候，同時刪除hashset中和當前元素的位置差已經超過k的對應元素。這樣就可以減少后序查找的時間。

這樣只要新遍歷到的元素的值已經存在于hashset之中，我們就可以斷定，這兩個元素的位置差一定是小于k的了。

解法

        int length = nums.length;
        if(length<=1) return false;
        Set count = new HashSet();
        
        for(int i=0;i k){
                count.remove(nums[i-k-1]);
            }
            if(!count.add(nums[i])){
                return true;
            }
        }
        return false;

GPU云服務器云服務器 Contains DUPLICATE Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68394.html

leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
leetcode217.219.220 contains duplicate

摘要：輸入一個整數數組，查看數組中是否存在重復的值。新的數組中數組的下標為原數組的值，如果遍歷過，則設置為。這里使用了作為實現的數據結構，通過堆的形式對集合中的數據進行存儲，從而我們可以通過某種順序獲得該集合中的所有順序。 217 Contains Duplicate Given an array of integers, find if the array contains any dup...

tulayang 2019-08-16 10:56 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
[LintCode/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 ...

894974231 2019-08-19 10:48 評論0 收藏0