[LeetCode] 548. Split Array with Equal Sum

frank_fun 发布于2019-08-16 13:50 / 2030人阅读

Problem

Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions:

0 < i, i + 1 < j, j + 1 < k < n - 1
Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.
where we define that subarray (L, R) represents a slice of the original array starting from the element indexed L to the element indexed R.
Example:
Input: [1,2,1,2,1,2,1]
Output: True
Explanation:
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
Note:
1 <= n <= 2000.
Elements in the given array will be in range [-1,000,000, 1,000,000].

Solution

class Solution {
    public boolean splitArray(int[] nums) {
        if (nums == null || nums.length < 7) return false;
        int len = nums.length;
        int[] sum = new int[len];
        sum[0] = nums[0];
        for (int i = 1; i < len; i++) {
            sum[i] = sum[i-1]+nums[i];
        }
        // 0 ~ i-1  |  i+1 ~ mid-1  |  mid+1 ~ k-1  |  k+1 ~ len-1
        for (int mid = 3; mid < len-3; mid++) {
            Set set = new HashSet<>();
            for (int i = 1; i <= mid-2; i++) {
                //save quarter sum into hashset
                if (sum[i-1] == sum[mid-1]-sum[i]) set.add(sum[i-1]);
            }
            for (int k = mid+2; k <= len-2; k++) {
                if (sum[len-1]-sum[k] == sum[k-1]-sum[mid]) {
                    int quarterSum = sum[len-1]-sum[k];
                    if (set.contains(quarterSum)) return true;
                }
            }
        }
        return false;
    }
}

云服务器 GPU云服务器 equal LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72407.html

【译】45种Javascript技巧大全

摘要：对进行序列化和反序列化避免使用和构造函数使用和构造函数是非常昂贵的操作，因为每次他们都会调用脚本引擎将源代码转换成可执行代码。原文：45 Useful JavaScript Tips, Tricks and Best Practices 译文：45个有用的JavaScript技巧，窍门和最佳实践译者：dwqs 在这篇文章中，我将分享一些JavaScript常用的技巧，窍门和最...

hufeng 2019-08-21 10:25 评论0 收藏0
45 个实用的 JavaScript 技巧、窍门和最佳实践

摘要：使用闭包实现私有变量译者添加未在构造函数中初始化的属性在语句结尾处使用分号在语句结尾处使用分号是一个很好的实践。总结我知道还有很多其他的技巧，窍门和最佳实践，所以如果你有其他想要添加或者对我分享的这些有反馈或者纠正，请在评论中指出。 showImg(http://segmentfault.com/img/bVbJnR); 如你所知，JavaScript是世界上第一的编程语言(编者注：2...

魏宪会 2019-08-21 12:06 评论0 收藏0
JavaScript编程注意事项、技巧大全

摘要：数组元素删除应使用。用来序列化与反序列化结果为的值与对象相同不要使用或者函数构造器和函数构造器的开销较大，每次调用，引擎都要将源代码转换为可执行的代码。收藏自 JavaScript奇技淫巧45招 JavaScript是一个绝冠全球的编程语言，可用于Web开发、移动应用开发（PhoneGap、Appcelerator）、服务器端开发（Node.js和Wakanda）等等。JavaSc...

Shimmer 2019-08-21 10:24 评论0 收藏0
[LeetCode] 663. Equal Tree Partition

Problem Given a binary tree with n nodes, your task is to check if its possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tr...

coordinate35 2019-08-16 13:48 评论0 收藏0
[LeetCode] 698. Partition to K Equal Sum Subsets

Problem Given an array of integers nums and a positive integer k, find whether its possible to divide this array into k non-empty subsets whose sums are all equal. Example 1:Input: nums = [4, 3, 2, 3,...

kuangcaibao 2019-08-16 13:41 评论0 收藏0