“””
You and a friend have received a special gold chain as a gift.
The chain links each have an integer weight, not necessarily the same.
You and your friend must choose one of the links to be removed and provided to charity, after which the chain will be reconnected.
After that, you can choose one place along the chain to split it in two, such that it creates two equally-weighted sections for you and your friend to take home.
For a given input chain (list of link weights), determine if a solution is possible.
“””
这道谷歌真题中，每个链环都有一个整数重量，而且彼此不一定相同。你和朋友先要选出一节链环捐给慈善机构，然后把剩下的链子重新接好，再从某个位置剪开成两段，希望这两段的总重量完全相同。给定链子每一环的重量列表，需要判断是否存在一种“先捐哪一环”和“在哪里剪开”的组合，使得最终两段重量相等。实现上要想办法用前缀和、总和等信息快速判断可行性，避免对所有删除位置和切割位置做爆炸式枚举。
正文完
