686 . 密室逃脫
TopCoder
Tags
Description
你和朋友一行 $N$ 人被困在密室中，提示上寫道「人山人海，$M$ 斤八兩」並放著一個體重計，你馬上意識到要取前兩個字解讀，也就是放上三個總和 $M$ 斤的人。
然而你卻好奇有多少通關方式，因此你問了現場 $N$ 個人的體重，並想找出有多少種選出三人的方式總和剛好是 $M$ 斤。請注意，兩人體重有可能會相同，此時他們仍算不同人。
Input Format
輸入第一行是兩個空白分隔的數字 $N, M$ 分別代表密室人數和目標總重。
第二行有 $N$ 個空白分隔的數字 $a_1, a_2, \dots, a_N$ ， 代表所有人分別幾斤。
$30\%$ 測資保證 $1\le N\le 200$ ， $1\le M, a_i\le 10^ 9$ 。
$70\%$ 測資保證 $1\le N\le 5000$ ， $1\le M, a_i\le 10^ 9$ 。
Output Format
輸出一行一個整數，代表有幾種選出三人的方法可以過關。
Sample Input 1
3 6
2 1 3
2 1 3
Sample Output 1
1
Sample Input 2
6 10
1 2 3 4 5 6
1 2 3 4 5 6
Sample Output 2
3
Hints
Problem Source
LeetCode 3Sum
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~9 | $1\le N\le 200$ | 30 |
| 3 | 0~15 | 無額外限制 | 70 |