:type A: List[int] :type target: int :rtype: int
(self, A, target)
| 79 | """ |
| 80 | class Solution(object): |
| 81 | def threeSumMulti(self, A, target): |
| 82 | """ |
| 83 | :type A: List[int] |
| 84 | :type target: int |
| 85 | :rtype: int |
| 86 | """ |
| 87 | mod = 10**9 + 7 |
| 88 | |
| 89 | def get_multiple(time, all_times): |
| 90 | if time==1: |
| 91 | return all_times |
| 92 | elif time==2: |
| 93 | return sum(range(all_times)) |
| 94 | elif time==3: |
| 95 | return sum(plus[:all_times]) |
| 96 | |
| 97 | x = {} |
| 98 | for j in set(A): |
| 99 | x[j] = A.count(j) |
| 100 | |
| 101 | maxes = max(x, key=lambda t: x[t]) |
| 102 | |
| 103 | plus = [sum(range(i)) for i in range(x[maxes])] |
| 104 | |
| 105 | |
| 106 | A = [] |
| 107 | |
| 108 | for i in sorted(x.keys()): |
| 109 | if x[i] > 3: |
| 110 | A.extend([i]*3) |
| 111 | else: |
| 112 | A.extend([i]*x[i]) |
| 113 | result = 0 |
| 114 | length = len(A) - 1 |
| 115 | sets = set() |
| 116 | for i in range(length): |
| 117 | t = target - A[i] |
| 118 | start = i+1 |
| 119 | end = length |
| 120 | |
| 121 | while start < end: |
| 122 | if A[start] + A[end] == t: |
| 123 | # pass |
| 124 | _ = [A[i], A[start], A[end]] |
| 125 | y = {e:_.count(e) for e in set(_)} |
| 126 | |
| 127 | _ = "{}{}{}".format(*_) |
| 128 | |
| 129 | if _ in sets: |
| 130 | start += 1 |
| 131 | continue |
| 132 | |
| 133 | c = 1 |
| 134 | for g in y: |
| 135 | c *= get_multiple(y[g], x[g]) |
| 136 | result += c |
| 137 | sets.add(_) |
| 138 | start += 1 |