Учитывая целое число x и отсортированный массив a из N различных целых чисел, спроектируйте алгоритм с линейным временем, чтобы определить, существуют ли два разных индекса я и j такие, что a [i] + a [j] == x
Алгоритм линейного времени для 2-SUM
Ответ 1
Это тип Проблема суммы подмножества
Вот мое решение. Я не знаю, было ли это известно раньше или нет. Представьте себе 3D-график функции двух переменных я и j:
sum(i,j) = a[i]+a[j]
Для каждого i существует такой j, что a[i]+a[j] ближе всего к x. Все эти пары (i,j) образуют строку, близкую к x. Нам просто нужно идти по этой линии и искать a[i]+a[j] == x:
int i = 0;
int j = lower_bound(a.begin(), a.end(), x) - a.begin();
while (j >= 0 && j < a.size() && i < a.size()) {
int sum = a[i]+a[j];
if (sum == x) {
cout << "found: " << i << " " << j << endl;
return;
}
if (sum > x) j--;
else i++;
if (i > j) break;
}
cout << " not found\n";
Сложность: O (n)
Ответ 2
думайте в терминах дополнений.
итерации по списку, укажите для каждого элемента, что число, необходимое для доступа к X для этого числа. номер палки и дополнение в хэш. в то время как итерация проверки, чтобы увидеть, является ли номер или его дополнение в хэш. если это так, найдено.
edit: и, как у меня есть некоторое время, некоторый псевдоидный код.
boolean find(int[] array, int x) {
HashSet<Integer> s = new HashSet<Integer>();
for(int i = 0; i < array.length; i++) {
if (s.contains(array[i]) || s.contains(x-array[i])) {
return true;
}
s.add(array[i]);
s.add(x-array[i]);
}
return false;
}
Ответ 3
- Сначала выполните поиск первого значения, равного > ceil (x/2). Позволяет вызвать это значение L.
- Из индекса L найдите назад, пока не найдете другой операнд, соответствующий сумме.
Это 2 * n ~ O (n)
Это мы можем расширить до бинарного поиска.
-
Найдите элемент с использованием бинарного поиска, чтобы найти L, такой, что L является min (элементы в > ceil (x/2)).
-
Сделайте то же самое для R, но теперь с L в качестве максимального размера элементов, доступных для поиска в массиве.
Этот подход 2 * log (n).
Ответ 4
Здесь используется версия python с использованием структуры данных словаря и номера. Это имеет линейное время работы (порядок N: O (N)):
def twoSum(N, x):
dict = {}
for i in range(len(N)):
complement = x - N[i]
if complement in dict:
return True
dict[N[i]] = i
return False
# Test
print twoSum([2, 7, 11, 15], 9) # True
print twoSum([2, 7, 11, 15], 3) # False
Ответ 5
Итерации по массиву и сохранение на карте квалифицированных номеров и их индексов. Сложность этого алгоритма равна O (n).
vector<int> twoSum(vector<int> &numbers, int target) {
map<int, int> summap;
vector<int> result;
for (int i = 0; i < numbers.size(); i++) {
summap[numbers[i]] = i;
}
for (int i = 0; i < numbers.size(); i++) {
int searched = target - numbers[i];
if (summap.find(searched) != summap.end()) {
result.push_back(i + 1);
result.push_back(summap[searched] + 1);
break;
}
}
return result;
}
Ответ 6
Я бы просто добавил разницу в HashSet<T> следующим образом:
public static bool Find(int[] array, int toReach)
{
HashSet<int> hashSet = new HashSet<int>();
foreach (int current in array)
{
if (hashSet.Contains(current))
{
return true;
}
hashSet.Add(toReach - current);
}
return false;
}
Ответ 7
Примечание. Код мой, но тестовый файл не был. Кроме того, эта идея для хэш-функции исходит из различных чтений в сети.
Реализация в Scala. Он использует hashMap и настраиваемое (но простое) сопоставление значений. Я согласен, что он не использует отсортированный характер исходного массива.
Хеш-функция
Я фиксирую размер ведра, разделив каждое значение на 10000. Это число может меняться в зависимости от размера, который вы хотите для ковшей, который может быть оптимальным в зависимости от диапазона ввода.
Так, например, ключ 1 отвечает за все целые числа от 1 до 9.
Влияние на область поиска
Что это значит, это то, что для текущего значения n, для которого вы хотите найти дополнение c, такое как n + c = x (x - элемент, который вы пытаетесь найти в 2-SUM), существует только 3 возможных ведра, в которых дополнение может быть:
- -key
- -key + 1
- -key - 1
Скажем, что ваши номера находятся в файле следующего вида:
0
1
10
10
-10
10000
-10000
10001
9999
-10001
-9999
10000
5000
5000
-5000
-1
1000
2000
-1000
-2000
Здесь реализация в Scala
import scala.collection.mutable
import scala.io.Source
object TwoSumRed {
val usage = """
Usage: scala TwoSumRed.scala [filename]
"""
def main(args: Array[String]) {
val carte = createMap(args) match {
case None => return
case Some(m) => m
}
var t: Int = 1
carte.foreach {
case (bucket, values) => {
var toCheck: Array[Long] = Array[Long]()
if (carte.contains(-bucket)) {
toCheck = toCheck ++: carte(-bucket)
}
if (carte.contains(-bucket - 1)) {
toCheck = toCheck ++: carte(-bucket - 1)
}
if (carte.contains(-bucket + 1)) {
toCheck = toCheck ++: carte(-bucket + 1)
}
values.foreach { v =>
toCheck.foreach { c =>
if ((c + v) == t) {
println(s"$c and $v forms a 2-sum for $t")
return
}
}
}
}
}
}
def createMap(args: Array[String]): Option[mutable.HashMap[Int, Array[Long]]] = {
var carte: mutable.HashMap[Int,Array[Long]] = mutable.HashMap[Int,Array[Long]]()
if (args.length == 1) {
val filename = args.toList(0)
val lines: List[Long] = Source.fromFile(filename).getLines().map(_.toLong).toList
lines.foreach { l =>
val idx: Int = math.floor(l / 10000).toInt
if (carte.contains(idx)) {
carte(idx) = carte(idx) :+ l
} else {
carte += (idx -> Array[Long](l))
}
}
Some(carte)
} else {
println(usage)
None
}
}
}
Ответ 8
int[] b = new int[N];
for (int i = 0; i < N; i++)
{
b[i] = x - a[N -1 - i];
}
for (int i = 0, j = 0; i < N && j < N;)
if(a[i] == b[j])
{
cout << "found";
return;
} else if(a[i] < b[j])
i++;
else
j++;
cout << "not found";
Ответ 9
Здесь представлено решение линейной временной сложности O (n) время O (1) пространство
public void twoSum(int[] arr){
if(arr.length < 2) return;
int max = arr[0] + arr[1];
int bigger = Math.max(arr[0], arr[1]);
int smaller = Math.min(arr[0], arr[1]);
int biggerIndex = 0;
int smallerIndex = 0;
for(int i = 2 ; i < arr.length ; i++){
if(arr[i] + bigger <= max){ continue;}
else{
if(arr[i] > bigger){
smaller = bigger;
bigger = arr[i];
biggerIndex = i;
}else if(arr[i] > smaller)
{
smaller = arr[i];
smallerIndex = i;
}
max = bigger + smaller;
}
}
System.out.println("Biggest sum is: " + max + "with indices ["+biggerIndex+","+smallerIndex+"]");
}
Ответ 10
Решение
- Нам нужен массив для хранения индексов
- Убедитесь, что массив пуст или содержит менее 2 элементов.
- Определите начало и конечную точку массива
- Итерация до состояния выполняется
- Проверьте, равна ли сумма цели. Если да, получите индексы.
- Если условие не выполняется, перейдите влево или вправо на основе значения суммы
- Перемещение вправо
- Перемещение влево
Для получения дополнительной информации: [http://www.prathapkudupublog.com/2017/05/two-sum-ii-input-array-is-sorted.html
Ответ 11
Кредит леониду
Его решение в java, если вы хотите дать ему шанс
Я удалил return, поэтому, если массив отсортирован, но DOES разрешает дубликаты, он все равно дает пары
static boolean cpp(int[] a, int x) {
int i = 0;
int j = a.length - 1;
while (j >= 0 && j < a.length && i < a.length) {
int sum = a[i] + a[j];
if (sum == x) {
System.out.printf("found %s, %s \n", i, j);
// return true;
}
if (sum > x) j--;
else i++;
if (i > j) break;
}
System.out.println("not found");
return false;
}