sosodemonai https://blog.hatena.ne.jp/sosodemonai/ Neunomizuの日記 https://propyon.hateblo.jp/ leetcode tags: leetcode 問題 Explore Problems アイデア 整数の配列numsが与えられたとき，abs(nums[i] - nums[j]) <= tかつabs(i - j) <= kであるようなiとjがあるかを探せという問題です． 解法 まずtは非負なのでその時点でFalseを返します 連想配列cache[numをt+1で割った商] = numを用意します． $[0, t], [t + 1, 2t + 1], [2t + 2, 3t + 2]$と$t + 1$ごとで区切って連想配列内で記録します．計算を記録することで計算する回数を減らします． 例えばt = 4でnum =… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpropyon.hateblo.jp%2Fentry%2F2020%2F04%2F24%2F193413" title="# LeetCode Medium 220. Contains Duplicate III - Neunomizuの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-04-24 19:34:13 rich https://propyon.hateblo.jp/entry/2020/04/24/193413 1.0 100%