题目描述：
Limak is an old brown bear who likes to play darts.
Limak just picked up an empty scorecard. He then threw a sequence of darts into a dartboard and for each dart he recorded the point value of the area it hit. You are given a int[] w containing the contents of Limak's scorecard: a sequence of point values.
Today there is a special jackpot. In order to win the jackpot, the player must present a scorecard with exactly four scores: (a, b, c, d). Additionally, these scores must be such that a*b*c = d. Note that order matters: the scores a, b, c, d must have been obtained in this particular order.
Limak wants to erase all but four scores from his scorecard in such a way that he will win the jackpot. Compute and return the number of different ways in which he can do that.
题目大意：
Limak是一只喜欢玩飞镖的老棕熊。
Limak拿了一个空的记分卡，然后向记分卡投掷一组飞镖，并记录每次投掷的得分。给定一个int[]数组w，包含Limak的记分卡的内容：一组得分值。
今天设置了一个特别大奖。要赢得特别大奖，玩家必须提供一个包含4个得分（a, b, c, d）的记分卡。此外，这些得分必须满足a*b*c = d。注意需要考虑顺序：得分a, b, c, d必须以这个特定的顺序获取。
Limak想要从记分卡上擦去多余的得分只留下4个，来赢取大奖。计算并返回满足条件得分的可能方式。
解题思路：
时间复杂度O(n ^ 2)
1. 使用字典divDict统计d / c的个数（需要保证可以整除）
2. 计算d / c的值与a * b相互匹配，并且下标符合要求的a, b, c, d的个数
Python代码：
class BearDartsDiv2(object):
def count(self, w):
import collections
divDict = collections.defaultdict(int)
size = len(w)
for x in range(size):
for y in range(x + 1, size):
if w[y] % w[x] == 0:
divDict[w[y] / w[x]] += 1
ans = 0
for x in range(size):
for y in range(x + 1, size):
if w[y] % w[x] == 0:
divDict[w[y] / w[x]] -= 1
for y in range(x):
ans += divDict[w[x] * w[y]]
return ans
本文链接：http://bookshadow.com/weblog/2015/10/15/topcoder-srm-671-div2-bear-darts-div2/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
