Move Zeroes

問題概要

配列が与えられたとき、すべての 0 を右端に移動しつつ、非ゼロ要素の相対順序を保つ。新しい配列は作成不可。

解法

Remove Duplicates from Sorted Array と同様に、Two Pointer で解く。0 でない要素が現れたときだけ進むポインタ p を定義する。

public void moveZero(int[] nums) {
    int p = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[p] = nums[i];
            p++;
        }
    }

    while (p < nums.length) {
        nums[p] = 0;
        p++;
    }
}

この問題のポイントは「非ゼロ要素の移動」と「0 の補填」を 2 つのステップに分けること。時間計算量: O(n)、空間計算量: O(1)。

Intersection of Two Arrays II

問題概要

2 つの配列 nums1 と nums2 が与えられたとき、重複を含む共通部分（最大の部分集合）を返す。

解法

Solution 1

まず両配列をソートし、2 つのポインタで共通要素を探す方法。

public int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);

    List<Integer> result = new ArrayList<>();
    int i = 0, j = 0;

    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] > nums2[j]) {
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            result.add(nums1[i]);
            i++;
            j++;
        }
    }

    return result.stream().mapToInt(Integer::intValue).toArray();
}

ソートに O(n log n + m log m)、Two Pointer のスキャンに O(n + m) かかる。ポインタは前進するだけなので while ループの実行回数は最大 n + m 回。空間計算量は結果リストの O(min(n, m))。Java の Arrays.sort(int[]) は Dual-Pivot Quicksort でコールスタックが O(log n) だが、min(n, m) より十分小さいため無視できる。

Solution 2

HashMap を使って nums1 の各要素の出現回数を記録し、nums2 を走査して一致するものを集める方法。

public int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer, Integer> countMap = new HashMap<>();

    for (int num : nums1) {
        countMap.merge(num, 1, Integer::sum);
    }

    List<Integer> result = new ArrayList<>();

    for (int num : nums2) {
        int count = countMap.getOrDefault(num, 0);
        if (count > 0) {
            result.add(num);
            countMap.put(num, count - 1);
        }
    }

    return result.stream().mapToInt(Integer::intValue).toArray();
}

3Sum

問題概要

配列の中から合計が 0 になる 3 つの異なるインデックスの要素の組み合わせをすべて求める。

解法

Solution 1

最初に思いつくのは総当たり（3 重ループ）。合計が 0 の組み合わせが見つかったらソートして重複チェックをした上でリストに追加する。

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if ((nums[i] + nums[j] + nums[k]) == 0) {
                    List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k]);
                    temp.sort(Integer::compareTo);
                    if (!ret.contains(temp)) {
                        ret.add(temp);
                    }
                }
            }
        }
    }
    return ret;
}

時間計算量: O(n⁴)（contains による線形探索が加わるため）、空間計算量: O(n)。

Solution 2

ソート + Two Pointer を使ったより効率的な解法。

• 配列をソートして探索範囲を絞る。
• 重複しない各インデックス i に対して、j = i + 1・k = nums.length - 1 として while ループを回す。
• 合計が 0 より大きければ k--、小さければ j++、等しければ結果に追加し、次の重複しない j・k の値に進む。

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> returns = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum > 0) k--;
            if (sum < 0) j++;
            if (sum == 0) {
                returns.add(Arrays.asList(nums[i], nums[j], nums[k]));
                j++;
                k--;
                while (j < nums.length - 1 && nums[j] == nums[j - 1]) j++;
                while (k > j && nums[k] == nums[k + 1]) k--;
            }
        }
    }
    return returns;
}