链表或数组，如何解决这个que？

Question

我们将匹配的有序对定义如下：

给定一个整数K，(a，b)是匹配有序对当且仅当a+ b =K且a≤b。

我们得到一个由N个整数组成的数组。有些数组是好的，而另一些则是坏的。

问题的目的是检查给定的数组是否良好。

我们递归地定义一个好的数组:一个空数组是好的。考虑一个大小为2的数组a，b。当且仅当(a，b)是一个匹配的有序对时，这个数组才是好的。

注意:即使(b，a)匹配有序对，这个数组也不是很好。例如，如果K= 10，则数组2，8是好的，而数组7，3不是好的。包含在匹配有序对中的子数组是好的。注意:数组中匹配的有序对必须采用(ai，aj )的形式，其中i

下面是一些K=10的好数组的例子：

[1, 2, 3, 7, 8, 9], [1, 9, 3, 7], [1, 5, 5, 9, 3, 2, 8, 7]

以下是K=10的错误数组的一些示例：

[1, 2, 9, 8], [9, 2, 8, 1]

我不能解决这个实际问题。我应该如何处理这个问题？

Answer 1

进来的东西，一定要出来。我们可以这样写，[1, 5, 5, 9, 3, 2, 8, 7]为

[1, 5, 5, 9, 3, 2, 8, 7]
 (  (  )  )  (  (  )  )

使用相同的逻辑检查有效的括号。

Python代码：

def f(arr, k):
  stack = [arr[0]]

  for i in xrange(1, len(arr)):
    if stack:
      last = stack[ len(stack) - 1 ]
      if arr[i] >= last and arr[i] + last == k:
        print str(last) + ' ' + str(arr[i]) + ' match! Popping...'
        stack.pop()
        continue      
    stack.append(arr[i])

  return 'GOOD' if not stack else 'BAD'

输出：

=> f([1, 5, 5, 9, 3, 2, 8, 7], 10)
5 5 match! Popping...
1 9 match! Popping...
2 8 match! Popping...
3 7 match! Popping...
=> 'GOOD'

=> f([9, 2, 8, 1], 10)
2 8 match! Popping...
=> 'BAD'

Answer 2

1.取第一个元素，( a) 2.与所有其他元素(B)比较，检查其和是否为K(=10) 3.如果和为K(=10)，i)检查a<=b是否为真，然后从数组中删除a和b，并从step1中重复。ii)如果a<=b为false，那么它的数组是错误的。不需要进一步的步骤4.如果sum没有给出K(=10)，那么它的数组是错误的。不需要进一步的步骤