{"id":4515,"date":"2018-12-20T21:55:24","date_gmt":"2018-12-21T05:55:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4515"},"modified":"2018-12-20T21:55:34","modified_gmt":"2018-12-21T05:55:34","slug":"leetcode-220-contains-duplicate-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-220-contains-duplicate-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 220. Contains Duplicate III"},"content":{"rendered":"\n

Given an array of integers, find out whether there are two distinct indices i<\/em> and j<\/em> in the array such that the absolute<\/strong> difference between nums[i]<\/strong> and nums[j]<\/strong> is at most t<\/em> and the absolute<\/strong> difference between i<\/em> and j<\/em> is at most k<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>nums = [1,2,3,1], k = 3, t = 0
Output: <\/strong>true<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>nums = [1,0,1,1], k = 1, t = 2
Output: <\/strong>true<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input: <\/strong>nums = [1,5,9,1,5,9], k = 2, t = 3
Output: <\/strong>false<\/pre>\n\n\n\n
Solution: Sliding Window + Multiset (OrderedSet)<\/strong><\/h1>\n\n\n\n
Maintaining a sliding window of sorted numbers of k + 1. After the i-th number was inserted into the sliding window, check whether its left and right neighbors satisfy abs(nums[i] – neighbor) <= t<\/p>\n\n\n\n
Time complexity: O(nlogk)
Space complexity: O(k)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua, running time: 12 ms\nclass Solution {\npublic:\n  bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {\n    multiset s;\n    for (int i = 0; i < nums.size(); ++i) {\n      if (i > k)\n        s.erase(s.find(nums[i - k - 1]));\n            \n      auto it = s.insert(nums[i]);\n      if (it != begin(s) && *it - *prev(it) <= t)\n        return true;\n      if (next(it) != end(s) && *next(it) - *it <= t)\n        return true;\n    }\n    return false;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[177,335,215,185],"class_list":["post-4515","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-medium","tag-multiset","tag-sliding-window","tag-sorted","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4515","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4515"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4515\/revisions"}],"predecessor-version":[{"id":4517,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4515\/revisions\/4517"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4515"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4515"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4515"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}