Учитывая массив чисел, узнайте, составляют ли 3 из них в целом 0
Я не думаю, что Вы можете. Как @Michael Харен показал, можно использовать порядковые положения В пунктах ORDER BY, но я никогда не видел их используемый в другом месте в SQL Server.
я не уверен, какую проблему Вы имеете со своим одноразовым импортом данных, которому это помогло бы с - по-видимому, некоторое неудачное имя столбца? Можно ли объяснить немного больше?
3 ответа
Решение O (n ^ 2) без хэш-таблиц (потому что использование хеш-таблиц является обманом: P). Вот псевдокод:
Sort the array // O(nlogn)
for each i from 1 to len(array) - 1
iter = i + 1
rev_iter = len(array) - 1
while iter < rev_iter
tmp = array[iter] + array[rev_iter] + array[i]
if tmp > 0
rev_iter--
else if tmp < 0
iter++
else
return true
return false
В основном, используя отсортированный массив, для каждого числа (цели) в массиве вы используете два указателя: один начинается спереди, а другой - сзади массива, проверяется, соответствует ли сумма элементов указатели на это указывают>, <или == к цели, и соответственно продвигают указатели или возвращают истину, если цель найдена.
помещает отрицательные значения каждого числа в хеш-таблицу или какую-либо другую структуру данных поиска с постоянным временем. (n)
перебирает массив, получая каждый набор из двух чисел (n ^ 2), и проверяет, есть ли их сумма в хеш-таблице.
Не для похвалы или чего-то подобного, но вот моя версия решения Чарльза Ма на языке Python. Очень круто.
def find_sum_to_zero(arr):
arr = sorted(arr)
for i, target in enumerate(arr):
lower, upper = 0, len(arr)-1
while lower < i < upper:
tmp = target + arr[lower] + arr[upper]
if tmp > 0:
upper -= 1
elif tmp < 0:
lower += 1
else:
yield arr[lower], target, arr[upper]
lower += 1
upper -= 1
if __name__ == '__main__':
# Get a list of random integers with no duplicates
from random import randint
arr = list(set(randint(-200, 200) for _ in range(50)))
for s in find_sum_to_zero(arr):
print s
Намного позже:
def find_sum_to_zero(arr):
limits = 0, len(arr) - 1
arr = sorted(arr)
for i, target in enumerate(arr):
lower, upper = limits
while lower < i < upper:
values = (arr[lower], target, arr[upper])
tmp = sum(values)
if not tmp:
yield values
lower += tmp <= 0
upper -= tmp >= 0