923.md

923. 三数之和的多种可能 - 3Sum With Multiplicity

【双指针】 【桶排序】

Problem Link

给定一个整数数组 A，以及一个整数 target 作为目标值，返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。

由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。

Example:

示例 1：

输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20
解释：
按值枚举（A[i]，A[j]，A[k]）：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。

示例 2：

输入：A = [1,1,2,2,2,2], target = 5
输出：12
解释：
A[i] = 1，A[j] = A[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种情况，
从 [2,2,2,2] 中选出两个 2，有 6 种情况。

提示：

1. 3 <= A.length <= 3000
2. 0 <= A[i] <= 100
3. 0 <= target <= 300

Solutions

Solution 【桶排序】 ( 9ms)

class Solution {
  public int threeSumMulti(int[] A, int target) {
    long result = 0;
    long[] numbers = new long[101]; // 0 <= A[i] <= 100
    for (int i: A) {
      numbers[i]++;
    }
    int min = 0;
    while (numbers[min] == 0) {
      min++;
    }
    int max = 100;
    while (numbers[max] == 0) {
      max--;
    }
    int i = min;
    while (i <= max) {
      int j = min;
      while (j <= max) {
        int key = target - i - j;
        if (key >= i && key <= j && numbers[key] > 0) {
          if (i == j && i != key) {
            result += (numbers[i] * (numbers[i] - 1) / 2) * numbers[key];
          }else if (i == key && i != j) {
            result += numbers[j] * ((numbers[i] - 1) * numbers[i] / 2);
          }else if (j == key && i != j) {
            result += numbers[i] * ((numbers[j] - 1) * numbers[j] / 2);
          }else if (i == j && j == key) {
            result += numbers[i] * (numbers[i] - 1) * (numbers[i] - 2) / 6;
          }else{
            result += numbers[i] * numbers[j] * numbers[key];
          }
        }
        do {
          j++;
        } while (j < max && numbers[j] == 0);
      }
      do {
        i++;
      } while (i < max && numbers[i] == 0);
    }
    return (int)(result % 1000000007);
  }
}

Solution ( 7ms)

class Solution {
    public static int threeSumMulti(int[] A, int target) {
		long res = 0;
		int mod=1000000007;
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		int[] count = new int[101];
		for (int i = 0; i < A.length; i++) {
			count[A[i]]++;
			max = A[i] > max ? A[i] : max;
			min = A[i] < min ? A[i] : min;
		}
		for (int i = min; i <= max; i++) {
			if (count[i] == 0)
				continue;
			for (int j = i; j <= max; j++) {
				if (count[j] == 0)
					continue;
				int temp = target - i - j;
				if (temp >= j && temp <= max && count[temp] > 0) {
					res += getCount(i, j, temp, count[i], count[j], count[temp]);
				}
			}
		}
		return (int) (res % mod);
	}

	private static long getCount(int a, int b, int c, long i, long j, long k) {
		if (a == b) {
			if (b == c) {
				if (i < 3) {
					return 0;
				} else {
					return i * (i - 1)* (i - 2)  / 6;
				}
			} else {
				if (i < 2) {
					return 0;
				} else {
					return i * (i - 1) / 2 * k;
				}
			}
		} else if (b == c) {
			if (j < 2) {
				return 0;
			} else {
				return j * (j - 1) / 2 * i;
			}

		} else {
			return i * j * k;
		}
	}
}

Notes