HackerRank夏洛克与阵列性能

Question

我对HackerRank神探夏洛克和阵列测试做了这个小算法，但这在两个测试用例中得到了超时。这些测试用例创建了大量的列表，我无法看出性能方面有什么问题。

这就是问题所在：

沃森给夏洛克一个长度为NN的数组。然后，他要求他确定数组中是否存在一个元素，使其左边的元素之和等于其右侧元素的和。如果左边/右边没有元素，则将之和视为零。形式上，找一个ii，这样，AA1+A+A2.A.Ai-1 =A=Ai+1+A+Ai+2...A...AN。

输入格式第一行包含TT，测试用例的数量。对于每个测试用例，第一行包含NN，即数组AA中的元素数。每个测试用例的第二行包含NN空格分隔的整数，表示数组AA。

如果数组中存在一个元素，则每个测试用例的输出格式都会打印“是”，这样它左边的元素的和等于其右侧的元素之和；否则则打印“否”。

这是我的密码：

for turn in range(int(input())):
    lst_size = int(input())
    has_equal = False

    lst = list(map(int, input().split(" ")))

    if lst_size > 2:

        for i in range(lst_size):
            sumleft = sum(lst[:i])
            sumright = sum(lst[(i+1):])

            if sumleft == sumright:
                has_equal = True
                break

    if has_equal:
        print("YES")
    else:
        print("NO")

Answer 1

做一个和就像一次迭代，你只需要把它做一次，并且只做一次和。例如，您可以从列表的中心开始：

def test_list(lst):
    i = len(lst)/2
    sumleft = sum(lst[:i])
    sumright = sum(lst[i+1:])

    if sumleft==sumright:
        print "YES",i

    elif sumleft<sumright:
        print "going right"
        while(True):
            if sumleft==sumright:
                print "YES",i
                break
            if i==len(lst)-1 or sumleft>sumright :
                print "NO",i
                break
            sumleft += lst[i]
            sumright -= lst[i+1]
            i+=1

    else:
        print "going left"
        while(True):

            if sumleft==sumright:
                print "YES",i
                break
            if i==0 or sumleft<sumright :
                print "NO",i
                break
            sumright += lst[i]
            sumleft -= lst[i-1]
            i-=1



lst = [40,1,5,4,6,3,2,1,4,8,7,3,81]
test_list(lst)

结果：

> going right
> YES 11

Answer 2

我在O(n)时间内解决了这个问题，所有的测试用例都通过了。你可以用一点数学来驱动解方程。

假设我们有一个数组，它是随机数组{3,7,5,10,2,7,4,2}所以，该元素的存在使得所有元素的左侧之和等于右侧所有元素的和。

我假设这个元素是由y表示的，它存在于某个地方之间。所以，元素的左边部分用x表示，正如我所说，所有元素向左方向的和等于该元素右侧的所有元素之和。所以右边和也可以用x.So表示，我们可以很容易地说数组中所有元素的和应该等于x+y+x。

X+y+x=所有元素的和

所有元素的2x+ y=sum

2x=所有元素的和- y -> eq 1

如果我们有x和y，那么这个方程成立。这意味着，有一个元素是正确的，因为在这个方程中，我们必须不知道x和y，所以我们必须先得到x和y的值，然后将两个值都放在方程中，看看LHS是否等于RHS？LHS等于RHS，这意味着数组中存在一些元素，其中元素左侧的所有元素之和等于元素的右侧。让我们以一个示例数组为例。

{3,7,5,10,2,7,4,2}

首先，我将计算所有元素的和。

所有elements= 3+7+5+10+2+7+4+2和所有elements= 40的和

在eq 1中替换这个，您就会低于eq。

2x =40 - y -> eq 2

因为我们不知道y，但是y是肯定的，y将属于数组中的任何一个元素。因此，每次从数组中取出一个元素，并将y替换为像x这样的元素。我们将取基于y的x值，在这个问题中进行替换，看看LHS是否等于RHS。如果我们找到这样的一对x和y，其中LHS等于RHS。这意味着，数组中有一个元素，它保存了这个条件，我们将返回YES。

第一次迭代- {3,7,5,10,2,7,4,2}

y=3，x=0

只需在eq 2中替换这两个值，就可以进行种子处理。

0不等于37

现在向前移动指针，这次试一次

y=7，x=0+3=3

只需在eq 2中替换这两个值，就可以进行种子处理。

6不等于33

....so也这样做，直到找到满足这个条件的元素y。

现在跳过使用y=5进行下一次迭代并尝试使用y=10知道

如果y=10，x=3+7+5=15

只需在eq 2中替换这两个值，就可以进行种子处理。

30等于30。它意味着这是我们正在寻找的元素(Y)，其中左和等于右和。

下面是通过100%测试用例的代码。

static String balancedSums(List<Integer> arr) {
        int x = 0;
        int sum = 0;
        for (int a : arr) {
            sum += a;
        }

        for (int y : arr) {
            if (2 * x == sum - y) {
                return "YES";
            }
            x = x + y;
        }
        return "NO";

    }

仍然有疑问，你可以查看视频教程这里。

Answer 3

我只是试着用Python来解决这个问题。

这个问题要求找到一个元素(X)，其中(X)左边数组中的元素之和等于(X)右侧元素之和。

换句话说，前缀==和后缀之和。

这里所做的是，我获得了两个变量，它们将计数元素，一个从左边，一个从右边。

两个变量是。

从左到右计数然后..。将从右到左计数的"rev_count“。

另一个变量"temp“将存储第一个元素(基于0)。

我使用了一个while循环来设置一个条件，只要"temp“变量不是从右到左计数的元素之和的==。

(1)人数将增加到1.

(2) rev_count也将从右向左增加到1...decreasing。允许使用从左到右的元素之和更新temp的值。

这个过程是重复的，直到我们进入IF条件，如果我们找到元素，它会给出答案，如果我们没有找到，则给出"No“。

如果我们找到元素，它被表示为element+1，它是count+1，它在某种程度上是平衡数组的支点。

import numpy as np

d = [1, 4, 2, 5]
count = 0
rev_count = 2


temp = d[count]

while temp != sum(d[rev_count::]):
    rev_count += 1
    count += 1
    temp = temp + d[count]

np_array = np.array(d)
item_index = np.where(np_array==d[count+1])

if temp == sum(d[rev_count::]):
    print(d[count+1])
    print(item_index)

else:
    print("No")

元素的发现和元素的索引都是有效的。

任何反馈或批评都是welcomed...Thanks提供的机会。