LeetCoding Challenge Oct. 3: K-diff Pairs in an Array

公開:2020/10/04
更新:2020/10/22
2 min読了の目安(約1800字TECH技術記事

LeetCode October Challenge の 3 日目。

今日の問題は K-diff Pairs in an Array

問題の概要

  • 与えられた int の配列より、差がちょうど k となる要素の組 (重複を除く) を求める

実装の手順・考え方

  • 処理をしやすいように、int の配列は昇順にソートしてしまおう
    • Arrays.sort(int[]) を使えば、ソートにかかる時間計算量は O(n * log(n)) で済む
  • 数値が昇順に並んでいれば、いわゆる「しゃくとり法」が適用できるよね?
    • left と right の 2 つの変数で区間を表す
    • nums[right] - nums[left] <= k である限り、ひたすら right をインクリメントする
      • nums[right] - nums[left] == k となったときに K-diff pair を発見したことになる
        • 組の重複を除外する処置が必要になることに注意が必要
        • 後述するコード上では、incr の値でいい感じに組の重複を除外している
    • nums[right] - nums[left] >= k である限り、ひたすら left をインクリメントする
      • こちらも nums[right] - nums[left] == k となったときに K-diff pair を発見したことになる
        • left == right となるケースを除外することに注意が必要
  • 実装して submit → accept 🤗
    • Runtime は 3 ms で、これは Your runtime beats 100.00 % of java submissions. 🌟
    • ちなみに他の 3ms の実装をみると、もうちょっとシンプルに記述できるようだ。まだまだ精進が必要だ…

コード

class Solution {
    public int findPairs(int[] nums, int k) {
        if (nums.length <= 1) {
            return 0;
        }

        Arrays.sort(nums);

        int left = 0, right = 0;
        int result = 0;

        outer: while (right < nums.length - 1) {
            int incr = 1;
            int diff;
            while ((diff = nums[++right] - nums[left]) <= k) {
                if (diff == k) {
                    result += incr;
                    incr = 0;
                }
                if (right == nums.length - 1) {
                    break outer;
                }
            }

            incr = 1;
            while (left < right && (diff = nums[right] - nums[++left]) >= k) {
                if (diff == k && left < right) {
                    result += incr;
                    incr = 0;
                }
            }
        }

        return result;
    }
}