# 923 - 3Sum With Multiplicity

這題算是 3 Sum 系列最猛的變形了，先來看看也是用 Two Pointer 的解法一。

解法一 - Two Pointer

演算法的概念如下：

class Solution {
public:
    int threeSumMulti(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

        int count=0, n=nums.size(), MOD=(int)(1e9+7);
        for(int i=0; i<n; i++) {
            int l = i+1, r = n-1;

            while(l < r) {
                int sum = nums[i] + nums[l] + nums[r];

                if(sum < target) {
                    l++;
                }
                else if(sum > target) {
                    r--;
                }
                else if(nums[l] != nums[r]){
                    int lnum=1, rnum=1;

                    while(l+1<r && nums[l+1] == nums[l]) {lnum++; l++;}
                    while(r-1>l && nums[r-1] == nums[r]) {rnum++; r--;}

                    count += lnum*rnum;
                    count %= MOD;
                    l++;
                    r--;
                }
                else {
                    // M = k - j + 1
                    // We contributed M * (M-1) / 2 pairs.
                    count += (r-l+1) * (r-l) / 2;
                    count %= MOD;
                    break;
                }
            }

        }

        return count;
    }
};

解法二 - Hash Table

這個解法是參考 這篇討論，先記一下：

class Solution {
public:
    int threeSumMulti(vector<int>& nums, int target) {
        int ans = 0, mod = 1e9+7;

        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++) {
            ans = (ans + mp[target-nums[i]]) % mod;
            for(int j = 0; j < i; j++) mp[nums[i]+nums[j]]++;
        }

        return ans;
    }
};