You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

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

. 2 min read

【双指针】 【桶排序】

给定一个整数数组 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