leetcode——三数之和的多种可能（java）

给定一个整数数组 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 种情况。

解题方法：（相向双指针）

1.由题意得这道题可以使用相向双指针进行解题，并且题目涉及到和的问题，所以我们首先需要对数组进行排序，以便后面比较大小。

2.开始遍历数组，然后开始设定左右双指针分别为i+1和n-1，然后是老样子与target 开始比较，但是这道题到了相等这种情况之后我们要分成两种情况来讨论。

3.当我们检查到三数之和等于target时，我们需要开始细分为两种情况。

• 我们接下来的左右指针所指向的元素相等，所以我们直接将他们的数量利用组合公式计算出他们的组合数量（C(n, 2) = n * (n - 1) / 2）

• 如果不相等的话，我们需要讨论左右双指针他们所指的元素是否跟他们的下一个元素相等。

class Solution {
    private static final int mod = 1_000_000_007; 
    public int threeSumMulti(int[] arr, int target) {
        Arrays.sort(arr);
        int ans = 0;
        int n = arr.length;
        for (int i = 0; i < n - 2; i++) {
            int x = arr[i];
            if (x + arr[i + 1] + arr[i + 2] > target) break;
            if (x + arr[n - 1] + arr[n - 2] < target) continue;
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int sum = x + arr[j] + arr[k];
                if (sum > target) {
                    k--;
                } else if (sum < target) {
                    j++;
                } else {
                    if (arr[j] == arr[k]) {
                        int total = (k - j + 1) * (k - j) / 2;
                        ans += total;
                        ans = ans % mod;
                        break;
                    } else {
                        int m = j + 1, t = k - 1;
                        while (arr[j] == arr[m]) {
                            m++;
                        }
                        while (arr[k] == arr[t]) {
                            t--;
                        }
                        ans += (m - j) * (k - t);
                        ans = ans % mod;
                        j = m;
                        k = t;
                    }
                }
            }
        }
        return ans;
    }
}