Matsushita's Blog

しゃくとり法

配列における3つの要素の和

Problem leetcode.com 与えられた配列において、任意の3点の和がゼロとなる組合せを全て取得する問題。 Solution この問題は以下のように解くことができる。 任意の3点をstart, middle, endと置く(start < middle < end) startを固定し、middle = start + …

340. Longest Substring with At Most K Distinct Characters : Past Google Interview

Problem https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/ Given a string, find the length of the longest substring T that contains at most k distinct characters. For example, Given s = "eceba" and k = 2, T…

しゃくとり法を用いて計算量を減らす AtCoder C - 単調増加

問題 C: 単調増加 - AtCoder Beginner Contest 038 | AtCoder 解法 以下のようにしゃくり法を用いて計算量O(N)で算出する プラスされている箇所を見ると等差数列の和となっているので、等差数列の和の公式を用いることでさらに計算量を減らす事ができる。 ソ…