# 923 - 3Sum With Multiplicity

## 解法一 - 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;
}
};
``````