阿里秋招算法面试题全解析（带leetcode详解）

阿里巴巴面试题：同和分割数组

描述
给定一个有n个整数的数组，判断是否存在满足以下条件的三元组 (i, j, k):

1. 0 < i, i + 1 < j, j + 1 < k < n - 1
2. 子数组 (0, i - 1)， (i + 1, j - 1)， (j + 1, k - 1)和(k + 1, n - 1) 的和相等。
   定义子数组(L, R)表示原始数组从元素下标为L到R的那一段。
   如果存在这样的三元组，返回 true，否则返回 false。
3. 1 <= n <= 2000.
4. 给定数组中的元素的取值范围：[-1,000,000,1,000,000]

在线评测地址

样例1

输入: [1,3,2,1,3,2,1,3,2,1,3]
输出: true
解释: (2,5,8) => 四个子数组都是 [1,3]

样例 2:

输入: [1,2,1,2,1,2,1]
输出: true
解释: (1,3,5)

解题思路
首先枚举中间点 j, 把区间先分成两段.

1. 初始化一个空集合
2. 取左边的那段区间, 枚举点 i, 如果点i分隔出来的两段的和相同, 则把这个和放入一个集合中
3. 取右边的那段区间, 枚举点 k, 如果点k分隔出来的两段的和相同并且这个值也在集合中出