← 返回 google 的题目列表Golden Chain Split After Removing One Link
类型:online_judge
Problem: Split a Golden Chain After Removing One Link
You are given an integer array w representing the weights of consecutive links in a golden chain from left to right.
You must remove exactly one link (remove w[k]), then reconnect the remaining left and right parts into a single chain (i.e., the new chain becomes w[0..k-1] + w[k+1..n-1]).
Then you need to make one cut on this new chain so that it becomes two pieces (both pieces must be contiguous segments). If the total weights of the two pieces are equal, the chain can be evenly split.
Return:
True if there exists some index k to remove such that the reconnected chain can be evenly split
otherwise return False
Follow-up: Return all valid splitting methods, each represented by:
k: the removed index in the original array
c: the cut position in the reconnected chain (cut between indices c and c+1)
Constraints
1 <= n <= 2e5
1 <= w[i] <= 1e9
Examples / Tests
w = [1,2,3,3] → possible output: True
w = [1,1,1] → False
w = [5,5,5,5] → True
w = [2,1,4,2] → True/False depending on removal
w = [10] → False
Example
Input
4
1 2 3 3
Output
True