[LeetCode]Split Array with Equal Sum

DFS可以做，但是时间复杂度太高。也想过用值域上的binary search，给定sum k看数组能否按k等分成四份。如果数组全是正数的话这个方法应该可行，但是存在负数的话，从左边开始找和为k的subarray可能有多个，就不好做。所以我们还是分解成subproblems，分解成左右两快区间，分别找两个区间的equal sum，然后看有没有交集，这样的话时间复杂度是O(n^2)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	bool splitArray(vector<int>& nums) {
	int len = nums.size();
	if(len < 7)return false;
	for(int i = 3; i < len - 3; ++i)
	{
	unordered_set<int> set;
	//First half
	checkEqualSums(nums, 0, i - 1, set, false);
	//Second half
	if(checkEqualSums(nums, i + 1, len - 1, set, true))
	return true;
	}
	return false;
	}
	private:
	bool checkEqualSums(vector<int>& nums, int lo, int hi, unordered_set<int>& set, bool secondHalf)
	{
	if(hi - lo < 2)return false;
	int len = nums.size(), leftSum = 0, rightSum = 0;
	for(int i = lo + 1; i <= hi; ++i)
	rightSum += nums[i];
	for(int i = lo + 1; i <= hi - 1; ++i)
	{
	leftSum += nums[i - 1];
	rightSum -= nums[i];
	if(leftSum == rightSum)
	{
	if(!secondHalf)
	set.insert(leftSum);
	else
	{
	if(set.find(leftSum) != set.end())
	return true;
	}
	}
	}
	return false;
	}
	};

view raw Split Array with Equal Sum.cpp hosted with ❤ by GitHub