Leetcode-923 3Sum With Multiplicity(三数之和的多种可能)

 1 class Solution
 2 {
 3     private:
 4         int hashList[102];
 5     public:
 6         long long int get(long long int n,long long int m)
 7         {
 8             if(m==1)
 9                 return n;
10             else if(m==2)
11                 return (n*(n-1))/2;
12             else if(m==3)
13                 return (n*(n-1)*(n-2))/6;
14         }
15         int threeSumMulti(vector<int>& A, int target)
16         {
17             memset(hashList,0,sizeof(hashList));
18 
19             for(auto d:A)
20                 hashList[d] ++;
21 
22             long long int result = 0;
23             for(int i = 0; i <= target&&i<=100; i ++)
24             {
25                 if(hashList[i]>=3 && 3*i==target)
26                 {
27                     result += get(hashList[i],3);
28                     result %= 1000000007;
29                 }
30                 if(2*i<target && hashList[i]>=2)
31                 {
32                     if(target-2*i > i && target-2*i <= 100 && hashList[target-2*i])
33                     {
34                         result += hashList[target-2*i]*get(hashList[i],2);
35                         result %= 1000000007;
36                     //    cout << i << " " << i << " " << target-2*i << endl;
37                     }
38                 }
39                 if(hashList[i])
40                 {
41                     for(int j = i+1; j <= target && j<=100; j ++)
42                     {
43                         if(hashList[j]>=2 && 2*j+i==target)
44                         {
45                             result += hashList[i]*get(hashList[j],2);
46                             result %= 1000000007;
47                         //    cout << i << " " << j << " " << j << endl;
48                         }
49                         if(hashList[j])
50                         {
51                             if(target-i-j > j && target-i-j <= 100 && hashList[target-i-j])
52                             {
53                                 result += hashList[i]*hashList[j]*hashList[target-i-j];
54                                 result %= 1000000007;
55                             //    cout << i << " " << j << " " << target-i-j << endl;
56                             }
57                         }
58                     }
59                 }
60             }
61             result %= 1000000007;
62             return (int)result;
63         }
64 };