3Sum With Multiplicity Solutions in C++

/// Source : https://leetcode.com/problems/3sum-with-multiplicity/description/
/// Author : liuyubobobo
/// Time   : 2018-10-13

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Using HashMap and Combinations
/// Using Memory Search to calculate the combinations
///
/// Try to use Dynamic Programming to get the combinations table but MLE :-(
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {

private:
    int MOD = 1e9 + 7;

public:
    int threeSumMulti(vector<int>& A, int target) {

        map<int, int> freq;
        for(int a: A)
            freq[a] ++;

        vector<int> keys;
        for(const pair<int, int>& p: freq)
            keys.push_back(p.first);

        int res = 0;
        vector<vector<int>> comb(3001, vector<int>(3001, -1));
        for(int i = 0; i < keys.size(); i ++)
            for(int j = i; j < keys.size(); j ++){
                int a = keys[i], b = keys[j], c = target - keys[i] - keys[j];
                if(c >= b){
                    if(a == b && b == c)
                        res = (res + C(freq[a], 3, comb)) % MOD;
                    else if(a == b)
                        res = (res + (long long)C(freq[a], 2, comb) * freq[c]) % MOD;
                    else if(b == c)
                        res = (res + freq[a] * (long long)C(freq[b], 2, comb)) % MOD;
                    else
                        res = (res + freq[a] * freq[b] * freq[c]) % MOD;
                }
                else
                    break;
            }
        return res;
    }

private:
    int C(int m, int n, vector<vector<int>>& comb){

        if(n > m)
            return 0;

        if(n == 0 || m == n)
            return 1;

        if(comb[m][n] != -1)
            return comb[m][n];

        return comb[m][n] = (C(m - 1, n, comb) + C(m - 1, n - 1, comb)) % MOD;
    }
};


int main() {

    vector<int> A1 = {1,1,2,2,3,3,4,4,5,5};
    cout << Solution().threeSumMulti(A1, 8) << endl;
    // 20

    vector<int> A2 = {1,1,2,2,2,2};
    cout << Solution().threeSumMulti(A2, 5) << endl;
    // 12

    vector<int> A3(3000, 0);
    cout << Solution().threeSumMulti(A3, 0) << endl;
    // 495500972

    cout << sizeof("") << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/3sum-with-multiplicity/description/
/// Author : liuyubobobo
/// Time   : 2018-10-15

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Using HashMap and Combinations
/// Since we ony use combination numbers like C(n, 2) or C(n, 3),
/// There's no need to calculate the n * n combination tables,
/// We calculate a n * 3 combination table instead :-)
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

private:
    int MOD = 1e9 + 7;

public:
    int threeSumMulti(vector<int>& A, int target) {

        vector<vector<int>> C = calcC(A.size());

        map<int, int> freq;
        for(int a: A)
            freq[a] ++;

        vector<int> keys;
        for(const pair<int, int>& p: freq)
            keys.push_back(p.first);

        int res = 0;
        for(int i = 0; i < keys.size(); i ++)
            for(int j = i; j < keys.size(); j ++){
                int a = keys[i], b = keys[j], c = target - keys[i] - keys[j];
                if(c >= b){
                    if(a == b && b == c)
                        res = (res + C[freq[a]][3]) % MOD;
                    else if(a == b)
                        res = (res + (long long)C[freq[a]][2] * freq[c]) % MOD;
                    else if(b == c)
                        res = (res + freq[a] * (long long)C[freq[b]][2]) % MOD;
                    else
                        res = (res + freq[a] * freq[b] * freq[c]) % MOD;
                }
                else
                    break;
            }
        return res;
    }

private:
    vector<vector<int>> calcC(int n){

        vector<vector<int>> C(n + 1, vector<int>(4, 0));
        C[0][0] = 1;
        for(int i = 1; i <= n; i ++){
            C[i][0] = 1;
            for(int j = 1; j <= 4; j ++)
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
        return C;
    }
};


int main() {

    vector<int> A1 = {1,1,2,2,3,3,4,4,5,5};
    cout << Solution().threeSumMulti(A1, 8) << endl;
    // 20

    vector<int> A2 = {1,1,2,2,2,2};
    cout << Solution().threeSumMulti(A2, 5) << endl;
    // 12

    vector<int> A3(3000, 0);
    cout << Solution().threeSumMulti(A3, 0) << endl;
    // 495500972

    return 0;
}

/// Source : https://leetcode.com/problems/3sum-with-multiplicity/description/
/// Author : liuyubobobo
/// Time   : 2018-10-15

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Using HashMap and Combinations
/// Since we ony use combination numbers like C(n, 2) or C(n, 3),
/// There's no need to calculate any combination tables, actually :-)
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

private:
    int MOD = 1e9 + 7;

public:
    int threeSumMulti(vector<int>& A, int target) {

        map<int, int> freq;
        for(int a: A)
            freq[a] ++;

        vector<int> keys;
        for(const pair<int, int>& p: freq)
            keys.push_back(p.first);

        int res = 0;
        for(int i = 0; i < keys.size(); i ++)
            for(int j = i; j < keys.size(); j ++){
                int a = keys[i], b = keys[j], c = target - keys[i] - keys[j];
                if(c >= b){
                    if(a == b && b == c && freq[a] >= 3){
                        long long C = ((long long)freq[a] * (freq[a] - 1) * (freq[a] - 2) / 6) % (long long)MOD;
                        res = (res + C) % MOD;
                    }
                    else if(a == b && b != c && freq[a] >= 2){
                        long long C = freq[a] * (freq[a] - 1) / 2;
                        res = (res + C * freq[c]) % MOD;
                        continue;
                    }
                    else if(b == c && a != b && freq[b] >= 2){
                        long long C = freq[b] * (freq[b] - 1) / 2;
                        res = (res + freq[a] * C) % MOD;
                        continue;
                    }
                    else if(a != b && b != c)
                        res = (res + freq[a] * freq[b] * freq[c]) % MOD;
                }
                else
                    break;
            }
        return res;
    }
};


int main() {

    vector<int> A1 = {1,1,2,2,3,3,4,4,5,5};
    cout << Solution().threeSumMulti(A1, 8) << endl;
    // 20

    vector<int> A2 = {1,1,2,2,2,2};
    cout << Solution().threeSumMulti(A2, 5) << endl;
    // 12

    vector<int> A3(3000, 0);
    cout << Solution().threeSumMulti(A3, 0) << endl;
    // 495500972

    vector<int> A4 = {2, 1, 3};
    cout << Solution().threeSumMulti(A4, 6) << endl;
    // 1

    vector<int> A5 = {3, 3, 0, 0, 3, 2, 2, 3};
    cout << Solution().threeSumMulti(A5, 6) << endl;
    // 12

    return 0;
}

/// Source : https://leetcode.com/problems/3sum-with-multiplicity/description/
/// Author : liuyubobobo
/// Time   : 2018-10-16

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Three Pointers
/// Based on Two Pointers Algorithm in 2-Sum Problem
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)
class Solution {

private:
    int MOD = 1e9 + 7;

public:
    int threeSumMulti(vector<int>& A, int target) {

        sort(A.begin(), A.end());

        int res = 0;
        for(int i = 0; i < A.size(); i ++){

            int t = target - A[i];
            int j = i + 1, k = A.size() - 1;
            while(j < k){
                if(A[j] + A[k] < t)
                    j ++;
                else if(A[j] + A[k] > t)
                    k --;
                else{
                    if(A[j] != A[k]){
                        int jj = j + 1;
                        for(; jj < A.size() && A[jj] == A[j]; jj ++);

                        int kk = k - 1;
                        for(; kk >= 0 && A[kk] == A[k]; kk --);

                        res = (res + (jj - j) * (k - kk)) % MOD;
                        j = jj;
                        k = kk;
                    }
                    else{
                        res = (res + (k - j + 1) * (k - j) / 2) % MOD;
                        break;
                    }
                }
            }
        }
        return res;
    }
};


int main() {

    vector<int> A1 = {1,1,2,2,3,3,4,4,5,5};
    cout << Solution().threeSumMulti(A1, 8) << endl;
    // 20

    vector<int> A2 = {1,1,2,2,2,2};
    cout << Solution().threeSumMulti(A2, 5) << endl;
    // 12

    vector<int> A3(3000, 0);
    cout << Solution().threeSumMulti(A3, 0) << endl;
    // 495500972

    vector<int> A4 = {2, 1, 3};
    cout << Solution().threeSumMulti(A4, 6) << endl;
    // 1

    vector<int> A5 = {3, 3, 0, 0, 3, 2, 2, 3};
    cout << Solution().threeSumMulti(A5, 6) << endl;
    // 12

    return 0;
}