給定一個整數數組 arr ，以及一個整數 target 作為目標值，返回滿足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元組 i, j, k 的數量。
由于結果會非常大，請返回 109 + 7 的模。
示例 1：
輸入：arr = [1,1,2,2,3,3,4,4,5,5], target = 8
輸出：20
解釋：
按值枚舉(arr[i], arr[j], arr[k])：
(1, 2, 5) 出現 8 次；
(1, 3, 4) 出現 8 次；
(2, 2, 4) 出現 2 次；
(2, 3, 3) 出現 2 次。
示例 2：
輸入：arr = [1,1,2,2,2,2], target = 5
輸出：12
解釋：
arr[i] = 1, arr[j] = arr[k] = 2 出現 12 次：
我們從 [1,1] 中選擇一個 1，有 2 種情況，
從 [2,2,2,2] 中選出兩個 2，有 6 種情況。
提示：
3 <= arr.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300
先對arr進行排序，然后固定一個數字，進行相向雙指針計算即可：
class Solution {
public:int threeSumMulti(vector<int>& arr, int target) {long long ans = 0;sort(arr.begin(), arr.end());// 每次固定一個數字for (int i = 0; i < arr.size() - 2; ++i) {int left = i + 1;int right = arr.size() - 1;if (arr[i] + arr[i + 1] + arr[i + 2] > target) {break;}if (arr[i] + arr[right] + arr[right - 1] < target) {continue;}while (left < right) {if (arr[i] + arr[left] + arr[right] > target) {--right;} else if (arr[i] + arr[left] + arr[right] < target) {++left;} else {// 如果left和right指向的數字的值相同// 說明[left, right]中任意兩數字加arr[i]的和都為targetif (arr[left] == arr[right]) {ans += (right - left + 1) * (right - left) / 2;break;}// 計算左指針指向的數字有多少個連續相同的int leftSame = 1;++left;while (arr[left] == arr[left - 1]) {++leftSame;++left;}// 計算右指針指向的數字有多少個相同的int rightSame = 1;--right;while (arr[right] == arr[right + 1]) {++rightSame;--right;}ans += leftSame * rightSame;}}}return ans % (int)(1e9 + 7);}
};
如果arr的長度為n，則此算法時間復雜度為O(n2^22)，空間復雜度為O(logn)。
)
