Leetcode_Ex2: 数组之和三等分问题

1. 问题描述

该问题是leetcode上一道难易程度为easy的题目，原题如下：

Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i+1 < j with (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + A[j-1] + … + A[A.length - 1])

Example1
Input: [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2
Input: [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false

Example 3
Input: [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

给定一个整数数组，如果该数组可以被分为三个不为空的子数组，且三个数组的和相等，则满足要求，否则不满足要求。如：数组为[0,2,1,-6,6,-7,9,1,2,0,1]，则可以分为数组[0, 2, 1]、[-6, 6, -7, 9]和[2, 0, 1]，它们的和均为3。

2. 简单方法

针对该问题，我们很容易利用双重循环来实现，设定两个循环地址变量i和j，遍历i和j的组合，找到????A[0:i]和A[i:j]及A[j:]相等的i和j即可，复杂度为O(n^2)，示例代码如下：

class Solution(object):
    def canThreePartsEqualSum(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        array_sum = sum(A)
        if array_sum % 3 != 0:
            return False
        else:
            divide = array_sum / 3
            current_sum = 0
            ids = []
            for i in range(len(A)):
                current_sum += A[i]
                if current_sum == divide:
                    current_sum = 0
                    ids.append(i)
            if len(ids) == 3:
                return True
            else:
                return False

当针对Leetcode提供的较大的测试样例时，该代码运行速度较慢，提示"Time Limit Exceeded"。

3. 是否存在O(n)的算法？

让我们再来回顾一下问题：是否存在一种切分，得到三个和相等的子数组，略懂算法的小明说，他一定会这样做：

先计算出数组的总和array_sum，如果可以分为三部分，则一定可以被3整除，记为divide；
我沿着数组走，边走边记录当前的和到current_sum，如果达到了divide，就把当前数组id记录下来，把current_sum置为0；
继续前行，直到走到结尾。最后小明看看记了几个id，如果等于3个，不就表明可以分为3部分吗?
小明的方法不就是动态规划的最简版本吗，按着这个想法，python代码如下：

class Solution(object):
    def canThreePartsEqualSum(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        array_sum = sum(A)
        if array_sum % 3 != 0:
            return False
        else:
            divide = array_sum / 3
            current_sum = 0
            ids = []
            for i in range(len(A)):
                current_sum += A[i]
                if current_sum == divide:
                    current_sum = 0
                    ids.append(i)
            if len(ids) == 3:
                return True
            else:
                return False

这次我们再次提交，Leetcode给出了Accepted的提示，表明已经被认可了！

4. Go Go Go! 会更快吗?

抱着试试的态度，我们用Go语言重写了这个小代码，让我们看看Go的表现：

package main

import "fmt"

func partThreeArray(A []int) bool {
	var flag bool
	array_sum := sum_array(A)
	if array_sum % 3 != 0 {
		flag = false
	} else {
		divide := array_sum/3
		current_sum := 0
		count := 0
		for i := 0; i < len(A); i++{
			current_sum += A[i]
			if current_sum == divide {
				current_sum = 0
				count += 1
			}
		}
		if count == 3 {
			flag = true
		}
	}
	return flag
}

func sum_array(A []int) int {
	var sum int
	size := len(A)
	for i:=0; i<size; i++ {
		sum += A[i]
	}
	return sum
}

这里我们定义了两个子函数，其中sum_array用于计算数组的和，经过瞬间的等待，Leetcode返回给了我们结果：
Leetcode_Ex2: 数组之和三等分问题
可以看到，时间消耗快于100%的提交，空间占用小于100%的提交，Go Go Go！

Leetcode_Ex2: 数组之和三等分问题

1. 问题描述

2. 简单方法

3. 是否存在O(n)的算法？

4. Go Go Go! 会更快吗?

相关推荐