-
Notifications
You must be signed in to change notification settings - Fork 3
/
q0923.py
71 lines (67 loc) · 11 KB
/
q0923.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#!/usr/bin/python3
from typing import List
class Solution:
def threeSumMulti(self, A: List[int], target: int) -> int:
result:int = 0
dic = {}
for num in A:
if num in dic:
dic[num] += 1
else:
dic[num] = 1
keys = dic.keys()
for key_i in keys:
for key_j in keys:
key_k = target - key_i - key_j
if key_k in keys:
if key_i == key_j and key_j == key_k:
result += dic[key_i] * (dic[key_i] - 1) * (dic[key_i] - 2) // 6
elif key_i == key_j:
result += dic[key_i] * (dic[key_i] - 1) * dic[key_k] // 2
elif key_i < key_j < key_k:
result += dic[key_i] * dic[key_j] * dic[key_k]
result %= 1000000007
return result
def threeSumMulti2(self, A: List[int], target: int) -> int:
result = 0
nums = A
nums.sort()
length = len(nums)
for i in range(length):
tmp = target - nums[i]
left = i + 1
right = length - 1
while left < right:
sum = nums[left] + nums[right]
if sum == tmp:
# print("nums {} left {} ,right {}", nums[i], nums[left], nums[right])
if(nums[left] == nums[right]):
result += (right - left) * (right - left + 1) // 2
result %= 1000000007
left = right
# print(result)
else:
countLeft = 1
countRight = 1
left += 1
right -= 1
while left <= right and nums[left] == nums[left - 1]:
countLeft += 1
left += 1
while right >= left and nums[right] == nums[right + 1]:
countRight += 1
right -= 1
result += countLeft * countRight
result %= 1000000007
# print(result)
elif sum < tmp:
left += 1
else:
right -= 1
return result
solu = Solution()
nums = [62,37,68,44,92,88,60,94,75,19,0,28,86,4,51,79,92,26,34,95,26,63,3,14,9,35,80,30,43,9,85,86,67,14,68,36,22,9,86,87,20,44,67,7,29,54,73,1,83,99,55,94,66,9,6,36,2,53,5,36,25,39,26,92,72,94,36,85,30,81,43,10,60,84,47,55,18,58,62,85,24,67,81,89,18,61,43,70,1,45,87,28,81,57,59,99,66,17,6,38,15,2,50,57,30,69,1,18,59,5,91,52,58,12,19,68,20,24,33,3,73,81,83,4,26,21,93,41,92,92,84,0,17,86,65,80,93,79,9,92,86,28,91,7,80,56,72,29,76,84,21,52,79,1,19,72,66,43,44,3,65,21,65,85,42,27,57,11,53,93,70,3,80,80,73,74,80,14,37,98,58,14,28,47,83,60,0,19,79,15,78,23,35,94,36,90,56,38,2,46,48,33,64,85,64,81,25,50,59,52,81,22,3,100,74,88,83,66,65,50,94,56,26,49,45,3,13,63,10,26,19,14,28,87,23,85,91,6,41,87,79,100,73,57,68,13,74,86,74,31,39,7,59,74,28,98,69,58,71,65,2,52,64,40,5,21,25,76,9,5,34,33,99,22,21,100,19,53,8,1,80,19,21,0,90,67,73,9,4,13,99,27,82,56,27,70,84,83,46,74,11,6,32,85,84,79,15,4,15,76,39,32,53,85,94,98,4,51,38,12,40,19,36,96,70,17,42,25,1,52,68,31,17,19,96,0,48,72,24,54,38,35,65,10,41,69,11,70,49,100,26,27,7,42,16,0,30,57,37,1,46,50,4,7,81,46,44,69,71,86,29,86,92,98,2,69,43,19,40,90,28,29,58,23,59,41,65,26,16,10,32,83,9,42,92,50,13,14,4,23,19,21,26,17,50,22,16,36,45,4,68,17,33,64,88,87,62,91,27,39,32,11,16,71,68,77,70,90,92,57,20,95,56,31,73,68,42,22,53,17,18,50,24,82,53,52,7,96,8,40,45,75,49,24,39,51,39,15,81,59,90,22,55,3,11,48,13,40,14,37,28,94,47,85,69,48,41,94,6,46,93,91,34,45,35,50,40,16,77,71,67,36,17,19,10,62,12,74,18,51,30,85,58,27,43,38,20,61,14,53,96,4,83,89,4,99,53,23,61,37,14,87,60,19,5,59,50,49,50,41,51,44,99,37,52,11,70,79,84,19,70,34,72,37,19,18,99,36,10,77,14,72,36,13,67,77,8,79,59,0,62,43,66,63,35,20,73,91,54,91,40,18,12,90,73,24,62,50,60,76,69,79,65,34,85,23,96,93,69,12,84,70,75,47,46,61,77,56,38,22,4,15,77,77,72,20,34,45,50,4,85,51,81,66,92,53,64,47,88,6,92,8,67,11,36,82,12,86,0,42,20,59,20,12,32,36,69,25,40,2,81,60,12,52,71,21,5,18,3,79,60,52,21,99,72,4,87,86,77,67,66,95,96,20,62,45,86,42,37,6,22,3,90,49,71,62,64,47,6,52,86,73,79,38,67,15,10,40,26,32,12,13,93,66,95,70,95,55,66,60,54,58,13,44,39,56,66,93,36,71,94,86,52,26,26,31,1,49,82,75,34,65,7,79,98,37,23,68,72,93,50,71,91,30,14,18,92,15,91,8,8,77,93,57,97,92,12,81,3,94,32,21,59,15,88,89,4,8,46,46,75,36,52,76,61,0,44,84,87,72,99,43,36,32,38,73,23,91,79,7,39,18,46,47,9,57,4,3,63,2,98,28,71,92,39,47,49,80,61,83,98,53,9,48,64,85,61,56,25,98,89,31,84,57,66,29,91,56,57,78,68,21,69,75,33,90,90,42,66,65,94,20,82,78,6,54,41,90,10,32,80,72,25,53,51,98,29,82,56,92,80,5,70,69,99,75,97,17,26,38,40,96,59,57,82,60,72,25,0,32,40,81,1,62,66,77,41,62,49,17,32,69,20,42,15,8,45,35,24,75,28,80,60,48,54,70,82,19,64,16,5,68,55,1,19,86,77,21,95,38,72,16,78,10,75,9,24,28,36,40,72,98,93,64,10,52,35,65,97,31,35,59,32,64,85,99,51,19,84,14,12,55,12,4,67,42,73,30,38,11,18,8,38,73,2,3,47,0,5,54,98,22,5,27,9,23,26,65,11,41,62,22,59,45,94,49,13,15,72,35,100,50,63,83,80,13,75,18,26,53,61,16,99,22,96,17,5,87,75,96,11,51,8,92,34,92,69,31,92,66,94,88,57,77,48,21,53,13,60,87,63,9,55,46,38,27,51,38,21,66,34,50,60,4,68,3,74,91,33,53,21,66,69,25,74,0,14,60,29,33,7,30,97,66,14,48,69,66,6,68,71,7,4,83,69,61,65,88,74,55,79,94,16,63,10,14,0,42,60,11,42,28,22,67,94,43,11,90,85,24,19,18,51,26,1,35,56,51,66,16,100,80,94,86,11,22,47,4,69,44,45,93,90,19,55,70,38,70,74,36,42,27,50,23,30,22,75,1,16,33,79,56,38,30,77,57,81,44,43,55,1,59,47,68,21,75,23,11,80,73,82,39,68,95,64,34,99,59,75,23,8,98,16,68,84,12,97,79,5,2,74,46,59,32,20,89,73,17,75,31,93,58,10,89,9,91,40,54,48,17,80,38,10,37,85,100,90,68,21,2,20,94,38,63,95,97,2,56,10,60,42,15,21,23,76,82,65,18,58,75,89,68,90,62,37,51,64,30,1,4,86,68,55,100,63,38,54,80,64,25,54,22,36,95,11,27,33,52,45,61,45,41,13,27,69,87,23,96,37,27,46,16,39,71,9,58,49,22,1,28,74,12,43,10,63,71,11,79,44,14,65,93,5,96,19,61,83,73,4,0,43,0,18,27,78,53,67,36,7,82,91,90,47,70,4,91,21,12,24,66,2,16,22,10,80,86,61,33,21,32,58,33,67,50,99,10,69,72,75,36,83,30,11,81,92,35,63,56,95,69,20,10,22,87,77,23,31,90,92,18,63,39,66,41,74,75,3,84,74,88,13,19,72,77,40,92,83,62,16,96,17,2,54,86,84,41,46,39,16,9,27,60,42,49,72,88,88,80,49,11,9,84,45,97,21,19,17,3,38,84,26,82,76,70,41,83,51,57,87,28,59,92,0,43,84,17,1,74,43,11,43,26,97,8,53,0,71,42,54,99,18,27,40,47,22,18,76,87,16,98,70,9,77,93,57,71,81,12,47,10,83,92,69,27,10,59,61,69,89,31,88,41,33,21,2,45,60,36,69,25,94,29,5,57,64,95,86,45,60,98,35,88,9,73,64,78,83,18,98,7,45,72,69,69,77,84,15,76,37,94,62,100,72,85,34,13,73,99,38,89,28,20,74,68,35,71,28,91,71,2,17,9,94,24,74,10,6,55,92,5,96,43,72,62,49,93,24,61,2,95,89,47,21,80,59,62,89,75,9,57,100,89,12,18,95,22,20,82,65,55,30,3,53,48,50,84,67,10,78,18,39,1,99,37,41,31,44,93,54,78,20,63,33,6,45,57,57,57,43,38,29,42,88,5,38,92,71,45,51,42,12,1,87,69,85,27,42,52,94,76,34,1,85,54,60,79,12,39,38,60,60,21,21,57,1,52,40,60,30,32,30,62,9,31,76,90,5,14,31,17,10,32,41,41,12,70,26,79,57,88,94,76,15,80,72,16,15,72,14,62,26,39,17,4,0,43,13,46,65,50,28,46,80,81,65,90,78,33,88,71,67,77,64,21,36,100,23,84,57,94,72,73,80,25,7,14,31,99,17,62,74,93,55,21,92,86,90,26,98,84,39,72,57,53,72,29,56,27,67,94,64,91,3,89,37,70,69,73,81,92,16,6,42,40,16,42,19,65,64,13,41,68,83,60,91,36,12,87,80,69,68,93,15,62,59,74,67,75,13,66,24,33,54,19,82,32,57,40,74,10,70,42,78,94,77,30,71,21,14,1,48,46,16,90,20,40,64,27,85,47,32,26,67,76,70,75,77,26,56,57,52,39,72,30,85,0,63,42,97,27,28,0,32,97,50,34,53,92,39,6,21,91,9,58,100,17,53,19,85,58,56,19,100,40,79,50,46,28,71,36,17,6,89,72,10,4,22,88,54,6,49,63,84,5,81,82,65,95,46,24,79,47,83,0,50,18,26,77,46,60,100,88,11,35,68,59,79,20,51,2,20,78,96,31,98,27,99,36,14,49,79,38,44,90,57,82,57,42,37,88,27,25,11,58,7,97,10,34,40,37,33,55,88,91,54,9,79,11,32,61,51,87,80,19,20,55,59,44,74,86,28,68,69,82,74,24,78,55,70,84,49,82,33,54,2,2,15,49,69,82,16,14,99,29,84,19,42,48,51,46,61,94,64,90,90,18,10,3,63,67,5,74,68,73,64,8,7,46,9,6,65,66,80,68,15,14,40,57,63,37,5,5,46,77,79,92,29,16,85,8,98,10,86,47,95,27,42,46,82,81,7,50,60,80,76,35,85,43,58,33,49,23,98,12,52,88,55,43,70,62,26,41,79,54,32,84,21,68,14,57,51,10,83,48,69,91,0,17,34,54,53,44,40,33,37,42,93,11,53,79,54,31,57,98,56,24,80,10,42,36,60,35,49,8,98,88,16,11,39,27,61,24,34,57,52,1,34,55,52,22,72,88,90,90,71,18,81,89,71,25,26,61,11,15,3,42,98,8,56,14,12,39,84,98,68,7,10,32,15,59,80,55,81,8,95,17,43,7,40,43,5,98,68,37,38,17,57,59,31,90,49,12,48,8,30,63,24,80,60,22,17,13,46,76,83,75,2,15,100,96,33,44,68,53,19,30,11,1,97,36,8,28,96,73,76,82,40,8,19,17,32,73,55,33,18,83,43,53,89,70,8,88,95,61,49,55,75,30,61,53,57,67,86,6,86,16,13,55,16,69,56,60,69,17,51,75,22,26,97,68,1,68,39,17,9,87,60,76,100,7,88,17,16,77,3,52,70,67,68,42,73,13,43,16,91,100,77,79,27,45,77,16,17,25,38,24,85,64,40,92,7,35,42,1,40,47,31,98,79,36,72,27,89,96,44,34,47,59,55,60,21,32,89,76,16,91,87,25,26,66,45,92,92,4,20,30,98,91,53,31,62,33,96,24,12,18,65,69,23,35,46,39,40,62,68,29,32,89,42,17,49,72,65,43,50,25,3,21,77,97,33,9,12,28,37,48,55,82,1,12,57,15,44,78,74,16,5,100,4,78,94,58,3,98,33,72,39,8,76,12,91,41,18,74,40,93,48,61,26,73,46,91,95,49,69,44,4,20,84,86,63,21,9,42,26,34,97,23,85,44,52,70,26,53,4,39,61,91,92,63,62,7,89,46,65,15,91,96,60,54,13,71,5,18,9,55,39,36,28,60,21,78,83,98,43,82,6,35,33,35,17,68,15,2,5,6,66,42,63,66,45,71,44,14,89,19,50,48,57,62,51,7,66,36,90,73,86,89,9,87,29,93,46,61,98,5,86,26,9,76,36,18,92,14,58,2,34,36,69,81,93,1,11,68,84,43,1,40,20,82,87,80,44,37,66,24,100,66,37,22,39,79,63,48,28,2,21,78,83,54,98,51,54,37,100,50,31,13,18,55,61,15,1,23,69,67,74,99,62,31,61,54,47,84,64,72,76,72,58,96,60,28,83,29,28,1,7,54,67,95,15,60,21,100,48,64,17,76,30,36,44,10,42,23,57,34,79,38,55,41,67,7,90,6,93,92,11,27,55,94,33,8,84,24,80,65,100,5,89,1,81,82,56,64,39,34,52,63,46,46,63,71,100,85,89,2,95,67,87,87,91,42,20,28,12,52,53,90,38,58,68,60,70,85,56,79,40,57,5,53,12,18,43,44,8,68,49,63,1,20,39,91,85,94,62,14,97,28,28,65,47,100,69,99,53,93,70,3,18,1,34,28,78,100,71,21,55,10,90,35,85,48,71,35,88,100,77,95,26,71,14,89,84,86,95,34,48,37,57,20,46,19,3,7,88,29,71,16,99,39,92,54,43,63,74,98,93,97,72,43,29,26,22,26,9,88,45,91,88,79,24,14,29,9,85,69,47,78,7,48,85,48,72,35,17,25,8,18,58,59,49,87,10,37,44,32,10,56,31,6,42,35,99,72,14,71,51,13,67,38,62,14,54,36,85,16,73,100,63,94,98,52,61,39,4,21,24,26,43,5,98,72,82,33,94,2,22,28,3,54,58,31,82,46,19,31,88,50,8,31,72,66,0,55,88,80,6,17,19,27,66,68,32,67,14,11,46,85,13,49,24,57,95,97,53,30,80,35,34,44,46,24,58,85,58,45,66,55,23,51,67,31,74,33,95,74,19,53,21,71,6,86,96,92,53,66,24,74,23,6,30,24,0,1,51,66,1,12,67,7,38,42,14,77,30,88,25,73,46,66,2,84,100,2,43,19,18,25,99,26,69,16,21,67,9,62,72,90,55,67,49,27,25,80,84,63,89,9,46,80,65,47,40,54,91,41,69,62,2,21,94,48,72,100,46,86,45,67,96,45,65,38,71,93,58,93,35,80,30,76,78,61,37,37,45,42,38,94,83,57,97,5,33,66,13,9,46,30,1,82,53,52,28,98,94,56,63,78,14,49,69,39,51,46,17,21,14,13,54,44,14,84,13,88,4,33,69,96,98,61,74,43,27,26,56,7,97,15,7,7]
target = 184
result = solu.threeSumMulti(nums, target)
print(result)
28159267