Make writing a habit together! This is the 7th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

describe

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.

Example 1:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.
Copy the code

Example 2:

Input: ARr = [1,1,2,2,2,2], target = 5 Output: 12 Explanation: ARr [I] = 1, arr[j] = arr[k] = 2 Occurs 12 times: We choose one from [1,1] in 2 ways, and two 2s from [2,2,2] in 6 ways.Copy the code

Note:

3 <= arr.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300
Copy the code

parsing

Given an integer array arr and an integer target, return the number of triples I, j, k such that I < j < k and arr[I] + arr[j] + arr[k] == target. Since the answer is likely to be very large, it returns modulo 10^9 + 7.

The meaning of this problem is very simple, but it is a little difficult to solve. I looked at example 1 and thought it was very simple, but when I saw example 2, I was not calm. Although this problem is to examine permutations and combinations, there are still some holes in it. For example, three of the numbers a, B, and C may all be the same, two of them may be the same, or all three may be different, so we need to solve the problem in different cases.

Combined with the constraints, we know that the maximum length of ARR is 3000 and the maximum length of ARr [I] is 100, so we know that this problem allows time complexity O(N^2), and the process is as follows:

  • First count is used to count all the elements present in the ARR
  • Then double loop to find possible A and B, so that c is determined by target-a-b, if c is not valid to proceed directly to the next loop; If a, B and C are the same, then it is just a permutation of element A in ARR. If there are two identical numbers in a, B and C, then it is the number of permutations and combinations of elements a in ARr multiplied by the number of c; If a, B, and C are all different, then it is the product of the number of occurrences of the three elements in ARR;
  • Finally return 10 ** 9 + 7 modulo results can be

The time complexity is O(N^2) and the space complexity is O(N).

answer

class Solution(object): def threeSumMulti(self, arr, target): """ :type arr: List[int] :type target: int :rtype: Int """ result = 0 CNT = [0]*101 for n in arr: CNT [n] += 1 for a in range (0,101): for b in range (a,101): c = target - a - b if c < 0 or c > 100 : continue elif a == b and b == c: result += (cnt[a] * (cnt[a]-1) * (cnt[a]-2) )/ 6 elif a == b and b ! = c: result += (cnt[a] * (cnt[a]-1) ) / 2 * cnt[c] elif a < b and b < c : result += cnt[a] * cnt[b] * cnt[c] return int(result % mod)Copy the code

The results

Given in the linked list With Multiplicity. Memory Usage: 10000 ms Multiplicity for each node in Python online submissions.Copy the code

The original link

Leetcode.com/problems/3s…

Your support is my biggest motivation