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

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;
    }
}