4.6 Leetcodeにおける二つのポインタ手法

以下の問題はすべて二つのポインタを用いるものであり、加えて以下のケースも含まれる：

• Leetcode3: 最長の重複しない部分文字列（ハッシュテーブルの章で扱った）
• ホーソーのクイックソート
• 二分探索
• など

ゼロの移動 - Leetcode 283

public class ZeroMoveLeetcode283 {
    static void moveZeros(int[] nums) {
        int left = 0;
        int right = 0;
        while (right < nums.length) {
            if (nums[right] != 0) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeros(nums);
        System.out.println(Arrays.toString(nums));
    }
}

二数の和 II - Leetcode 167

public class TwoSumII {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
    }
    
    static public int[] twoSum(int[] numbers, int target) {
        return twoSum(numbers, 0, numbers.length - 1, target);
    }
    
    static int[] twoSum(int[] nums, int left, int right, int target) {
        int i = left;
        int j = right;
        while (i < j) {
            if (nums[i] + nums[j] < target) {
                i++;
            } else if (nums[i] + nums[j] > target) {
                j--;
            } else {
                break;
            }
        }
        return new int[]{i + 1, j + 1};
    }
}

Leetcode 1の二数の和との違いは、この問題では配列が昇順にソートされている点である。

三数の和 - Leetcode 15

public class ThreeSumLeetcode15 {

    static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        dfs(3, 0, nums.length - 1, 0, nums,
                new LinkedList<>(), result);
        return result;
    }

    static void dfs(int n, int i, int j, int target, int[] nums,
                    LinkedList<Integer> stack,
                    List<List<Integer>> result) {
        if (n == 2) {
            // 二数の和の問題を再利用
            twoSum(i, j, nums, target, stack, result);
            return;
        }
        for (int k = i; k < j - (n - 2); k++) {
            // 重複チェック
            if (k > i && nums[k] == nums[k - 1]) {
                continue;
            }
            // 一つの要素を固定し、残りのn-1個の和を求める
            stack.push(nums[k]);
            dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result);
            stack.pop();
        }
    }

    static int count;

    static public void twoSum(int i, int j, int[] numbers, int target,
                              LinkedList<Integer> stack,
                              List<List<Integer>> result) {
        count++;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum < target) {
                i++;
            } else if (sum > target) {
                j--;
            } else { // 解を見つけた
                ArrayList<Integer> list = new ArrayList<>(stack);
                list.add(numbers[i]);
                list.add(numbers[j]);
                result.add(list);
                // 他の解を探す
                i++;
                j--;
                while (i < j && numbers[i] == numbers[i - 1]) {
                    i++;
                }
                while (i < j && numbers[j] == numbers[j + 1]) {
                    j--;
                }
            }
        }
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int[] candidates = {-4, -1, -1, 0, 0, 1, 1, 2};
        System.out.println("データサイズ:" + candidates.length);
        System.out.println(threeSum(candidates));
        System.out.println("処理時間:" + (System.currentTimeMillis() - start));
        System.out.println("再帰回数:" + count);
    }
}

• この問題は以前の二数の和（Leetcode 1 および Leetcode 167）と異なる点は：
  • 二数の和では解答が一つだけであることが保証されているが、この問題ではすべての解答を求めなければならない
  • 重複を排除する必要がある
• この問題は組み合わせ総和 II（Leetcode 40）と似ているが、以下のような違いがある：
  • Leetcode 40は任意の数の和がtargetになる組み合わせをすべて求めるが、この問題は三数の和がtargetになる組み合わせをすべて求める
  • Leetcode 40ではバックトラッキングを用いた場合の時間計算量はO(2^n * n)だが、この問題では再帰の深さが限られているため、時間計算量はO(n^2)となる
• 最適化：固定する要素の位置を調整して、残りの要素が少なくとも2つ以上あるようにする。つまり、k < j - (n - 2)という条件を設ける

四数の和 - Leetcode 18

public class FourSumLeetcode18 {

    static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        dfs(4, 0, nums.length - 1, target, nums,
                new LinkedList<>(), result);
        return result;
    }

    static void dfs(int n, int i, int j, int target, int[] nums,
                    LinkedList<Integer> stack,
                    List<List<Integer>> result) {
        if (n == 2) {
            // 二数の和の問題を再利用
            twoSum(i, j, nums, target, stack, result);
            return;
        }
        for (int k = i; k < j - (n - 2); k++) { // 四数の和では i < j-2、三数の和では i < j-1
            // 重複チェック
            if (k > i && nums[k] == nums[k - 1]) {
                continue;
            }
            // 一つの要素を固定し、残りのn-1個の和を求める
            stack.push(nums[k]);
            dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result);
            stack.pop();
        }
    }

    static int count;

    static public void twoSum(int i, int j, int[] numbers, int target,
                              LinkedList<Integer> stack,
                              List<List<Integer>> result) {
        count++;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum < target) {
                i++;
            } else if (sum > target) {
                j--;
            } else { // 解を見つけた
                ArrayList<Integer> list = new ArrayList<>(stack);
                list.add(numbers[i]);
                list.add(numbers[j]);
                result.add(list);
                // 他の解を探す
                i++;
                j--;
                while (i < j && numbers[i] == numbers[i - 1]) {
                    i++;
                }
                while (i < j && numbers[j] == numbers[j + 1]) {
                    j--;
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
//        System.out.println(fourSum(new int[]{2, 2, 2, 2, 2}, 8));
//        System.out.println(fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, -294967296));
    }
}

最大の水量を持つ容器 - Leetcode 11

public class MaxWaterLeetcode11 {
    static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            int minHeight = Integer.min(height[left], height[right]);
            max = Integer.max(max, (right - left) * minHeight);
            while (left < right && height[left] <= minHeight) {
                left++;
            }
            while (left < right && height[right] <= minHeight) {
                right--;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
        System.out.println(maxArea(new int[]{2,1})); // 1
    }
}

文字列の逆順配置 - Leetcode 344

二つのポインタを用いた解法

public class ReverseStringLeetcode344 {
    public static void main(String[] args) {
        char[] array = "abcde".toCharArray();
        reverseString(array);
        System.out.println(Arrays.toString(array));
    }

    static void reverseString(char[] s) {
        recursion(s, 0, s.length - 1);
    }

    public static void recursion(char[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        swap(array, left, right);
        recursion(array, ++left, --right);
    }

    public static void swap(char[] array, int left, int right) {
        char temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}

• 初回の交換はarray[0]とarray[4]の間で行われる
• 2回目の交換はarray[1]とarray[3]の間で行われる
• 3回目にはi=j=2となり、再帰が終了する
• 配列の長さが偶数の場合、i>jになる時点で再帰が終了する