本文共 2450 字，大约阅读时间需要 8 分钟。

????????????????? i < j < k ? A[i] + A[j] + A[k] == target ?????????????????????????? 10^9 + 7 ????

????

????????????????????????????

???????????? O(n^2) ??????????????????? 300 ? 3000 ??????

????

import java.util.Arrays;public class Solution {    public int threeSumMulti(int[] nums, int target) {        Arrays.sort(nums);        int n = nums.length;        int mod = 1000000007;        int sum = 0;        int i, j, k;        for (i = 0; i < n - 2; i++) {            int start = i + 1;            int end = n - 1;            while (start < end) {                int current = nums[i] + nums[start] + nums[end];                if (current > target) {                    end--;                } else if (current < target) {                    start++;                } else {                    // current == target, calculate the number of valid triplets                    if (nums[start] == nums[end]) {                        // same values, choose any two from start to end                        int count = end - start + 1;                        sum = (sum + (count * (count - 1)) / 2) % mod;                        start++;                    } else {                        // different values, count the number of possible (j, k)                        int left = start;                        int right = end;                        int cnt = 0;                        while (left < right && nums[left] == nums[start]) {                            left++;                        }                        while (right > left && nums[right] == nums[end]) {                            right--;                        }                        int a = left - start;                        int b = right - end;                        cnt = a * b;                        sum = (sum + cnt) % mod;                        start++;                        end--;                    }                }            }        }        return sum % mod;    }}

????

????????????????????????????????????