equi-3 pair

发表于:2018-06-29 09:48:13
更新于:2018-06-29 09:48:13

A non-empty zero-indexed array A consisting of N positive integers is given. A pair of indices (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

The equi-3 pair is a pair of indices (X, Y), such that 0 < X, X + 1 < Y < N − 1, and the sums of slices (0, X−1), (X+1, Y−1), (Y+1, N−1) are all equal.

For example, consider array A such that:

A[0] = 4 A[1] = 5 A[2] = 1 A[3] = 1 A[4] = 1 A[5] = 1 A[6] = 4 A[7] = 3 A[8] = 1

Pair (1, 6) is an equi-3 pair, because the sums of slices (0, 0), (2, 5) and (7, 8) are all equal to 4. Pair (2, 4) is not an equi-3 pair, because although the sums of slices (0, 1) and (5, 8) are both equal to 9, the sum of the middle slice (3, 3) equals 1. There is only one equi-3 pair in this array.

The goal is to check whether array A contains an equi-3 pair. Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty zero-indexed array A consisting of N integers, returns 1 if array A contains an equi-3 pair and 0 otherwise.

For example, given array A shown above, the function should return 1, as explained above.

Assume that: ● N is an integer within the range [5..100,000]; ● each element of array A is an integer within the range [1..10,000].

Complexity: ● expected worst-case time complexity is O(N); ● expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

算法如下:

class Solution:
    def solution(self, A):
        N = len(A)
        s = A[0]

        for i in range(1, N):
            s += A[i]
            A[i] = s

        X = 1
        Y = N-2
        while X < Y:
            s1 = A[X-1]
            s2 = A[Y-1] - A[X]
            s3 = A[N-1] - A[Y]

            if s1 > s3:
                Y -= 1
            elif s1 < s3:
                X += 1
            elif s1 == s2 == s3:
                return 1
            else:
                X, Y = X+1, Y+1

        return 0


if __name__ == '__main__':
    A = [4, 5, 1, 1, 1, 1, 4, 3, 1]
    s = Solution()
    print(s.solution(A))