LeetCode 548. 将数组分割成和相等的子数组（哈希set）

Michael阿明

发布于 2021-02-19 10:53:34

1.9K0

发布于 2021-02-19 10:53:34

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

给定一个有 n 个整数的数组，你需要找到满足以下条件的三元组 (i, j, k) ：

0 < i, i + 1 < j, j + 1 < k < n - 1
子数组 (0, i - 1)，(i + 1, j - 1)，(j + 1, k - 1)，(k + 1, n - 1) 的和应该相等。

这里我们定义子数组 (L, R) 表示原数组从索引为L的元素开始至索引为R的元素。

示例:
输入: [1,2,1,2,1,2,1]
输出: True
解释:
i = 1, j = 3, k = 5. 
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1
 
注意:
1 <= n <= 2000。
给定数组中的元素会在 [-1,000,000, 1,000,000] 范围内。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/split-array-with-equal-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
public:
    bool splitArray(vector<int>& nums) {
    	int n = nums.size(), i, j, k;
    	if(n < 7) return false;
    	vector<int> sum(nums);
    	for(i = 1; i < n; i++)
    		sum[i] += sum[i-1];
    	for(j = 3; j < n-3; j++)
    	{
    		unordered_set<int> s;
    		for(i = 1; i < j-1; i++)
    		{
    			if(sum[i-1] == sum[j-1]- sum[i])
    				s.insert(sum[i-1]);
    		}
    		for(k = j+2; k < n-1; k++)
    		{
    			if(sum[k-1]-sum[j] == sum[n-1]-sum[k]
    				&& s.count(sum[k-1]-sum[j]))
    				return true;
    		}
    	}
    	return false;
    }
};

572 ms 11 MB

参考大佬的题解剪枝

作者：palading 链接：https://leetcode-cn.com/problems/split-array-with-equal-sum/solution/c-qian-zhui-he-jian-zhi-by-palading/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    bool splitArray(vector<int>& nums) {
    	int n = nums.size(), i, j, k;
    	if(n < 7) return false;
    	vector<int> sum(nums);
    	for(i = 1; i < n; i++)
    		sum[i] += sum[i-1];
        int maxnum = *max_element(nums.begin(), nums.end());
        int minnum = *min_element(nums.begin(), nums.end());
    	for(j = 3; j < n-3; j++)
    	{
    		if(abs(sum[n-1]-sum[j]-sum[j-1]) > maxnum-minnum)
    			continue;
    		unordered_set<int> s;
    		for(i = 1; i < j-1; i++)
    		{
    			if(sum[i-1] == sum[j-1]- sum[i])
    				s.insert(sum[i-1]);
    		}
    		for(k = j+2; k < n-1; k++)
    		{
    			if(sum[k-1]-sum[j] == sum[n-1]-sum[k]
    				&& s.count(sum[k-1]-sum[j]))
    				return true;
    		}
    	}
    	return false;
    }
};

8 ms 10.4 MB

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/08/07 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https