C++で解く3Sum Smaller問題：和がターゲット未満になる三つ組の数え方

問題概要

n個の整数からなる配列 nums とターゲット値 target が与えられたとき、インデックスの三つ組 (i, j, k) のうち、i, j, k がすべて 0 以上 n − 1 以下の範囲にあり、かつ nums[i] + nums[j] + nums[k] < target を満たすものの個数を求めます。

例えば、入力が nums = [-2, 0, 1, 3]、target = 2 の場合、出力は 2 になります。これは、和が 2 未満となる三つ組が [-2, 0, 1]（和は -1）と [-2, 0, 3]（和は 1）の 2 つ存在するためです。

解法のアプローチ

この問題は、配列をあらかじめソートしておき、二ポインタ（ツーポインタ）テクニックを組み合わせることで効率的に解けます。手順は以下の通りです。

• 答えを格納する変数 ret を 0 で初期化します
• 配列 a を昇順にソートします
• n を配列 a のサイズとします
• i を 0 から n − 3 まで 1 ずつ増やしながらループします
  • left := i + 1、right := n − 1 として初期化します
  • left < right の間、以下を繰り返します
    • sum := a[i] + a[left] + a[right] を計算します
    • sum < t の場合：配列がソート済みのため、left から right までのすべての要素との組み合わせが条件を満たします。そこで ret に right − left を加算し、left を 1 増やします
    • それ以外の場合：和が大きすぎるので、right を 1 減らします
• 最後に ret を返します

計算量

時間計算量は O(n²)（ソートに O(n log n)、二ポインタ探索全体で O(n²)）、空間計算量は O(1) です。すべての組み合わせを総当たりする素朴な O(n³) の解法と比べて大幅に高速化できるのがポイントです。

C++実装例

以下の実装を見ると理解が深まります。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int threeSumSmaller(vector<int>& a, int t) {
        int ret = 0;
        sort(a.begin(), a.end());
        int n = a.size();
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = a[i] + a[left] + a[right];
                if (sum < t) {
                    ret += right - left;
                    left++;
                }
                else {
                    right--;
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {-2, 0, 1, 3};
    cout << (ob.threeSumSmaller(v, 2));
}

入力

[-2,0,1,3] 2

出力

2

まとめ

この問題の鍵は、配列をソートすることで二ポインタ法を適用できる点にあります。三つの和がターゲット未満になった瞬間、left と right の間にある要素はすべて条件を満たすため、right − left 個を一括でカウントできます。これにより O(n³) の総当たり法を O(n²) まで高速化でき、大きな入力でも実用的な速度で動作します。