Это на Java: это даже удаляет возможные дубликаты. Время выполнения - O(n^2)

private static int[] intArray = {15,5,10,20,25,30};
private static int sum = 35;

private static void algorithm()
{
    Map<Integer, Integer> intMap = new Hashtable<Integer, Integer>();
    for (int i=0; i<intArray.length; i++) 
    {
        intMap.put(i, intArray[i]);
        if(intMap.containsValue(sum - intArray[i]))
            System.out.println("Found numbers : "+intArray[i] +" and "+(sum - intArray[i]));

    }
    System.out.println(intMap);
}

Шаг 1: отсортировать массив по O (n logn)

Шаг 2: Найти два индекса

0 < = i < j < = n в a [0. .n] такой, что a [i] + a [j] == k, где k - заданный ключ.

int i=0,j=n;
while(i<j) {
   int sum = a[i]+a[j];
   if(sum == k)
        print(i,j)
   else if (sum < k)
        i++;
   else if (sum > k)
        j--;
}

Этот вопрос пропускает еще некоторые детали в него. Как то, что является возвращаемым значением, ограничением на вход. Я видел некоторые вопросы, связанные, к который, который может быть этим вопросом с дополнительным требованием, to return the actual elements that result in the input

Вот моя версия решения, это должно быть O(n).

import java.util.*;

public class IntegerSum {

    private static final int[] NUMBERS = {1,2,3,4,5,6,7,8,9,10};

    public static void main(String[] args) {
        int[] result = IntegerSum.isSumExist(7);
        System.out.println(Arrays.toString(result));
    }

    /**
     * n = x + y
     * 7 = 1 + 6
     * 7 - 1 =  6
     * 7 - 6 = 1
     * The subtraction of one element in the array should result into the value of the other element if it exist;
     */
    public static int[] isSumExist(int n) {
        // validate the input, based on the question
        // This to return the values that actually result in the sum. which is even more tricky
        int[] output = new int[2];
        Map resultsMap = new HashMap<Integer, Integer>();
        // O(n)
        for (int number : NUMBERS) {
            if ( number > n )
                throw new IllegalStateException("The number is not in the array.");
            if ( resultsMap.containsKey(number) ) {
                output[0] = number;
                output[1] = (Integer) resultsMap.get(number);
                return output;
            }
            resultsMap.put(n - number, number);
        }
        throw new IllegalStateException("The number is not in the array.");
    }
}

Допустим, мы хотим найти два числа в массиве A, которые при сложении равны N.

1. Отсортируйте массив.
2. Найдите наибольшее число в массиве, которое меньше N / 2. Установите индекс этого числа как ниже .
3. Инициализировать верхний как нижний + 1.
4. Установить сумму = A [ нижний ] + A [ ] верхний ].
5. Если сумма == N, выполнено.
6. Если сумма верхний .
7. Если сумма > N, уменьшить меньше .
8. Если либо lower , либо upper находится вне массива, выполняется без совпадений.
9. Вернитесь к 4.

Сортировку можно выполнить за O (n log n). Поиск ведется за линейное время.

Используйте хеш-таблицу . Вставьте каждое число в свою хеш-таблицу вместе с его индексом. Затем пусть S будет вашей желаемой суммой. Для каждого числа array [i] в исходном массиве проверьте, существует ли в вашей хеш-таблице S - array [i] с индексом, отличным от i .

Средний случай - O (n) , наихудший случай - O (n ^ 2) , поэтому используйте решение двоичного поиска, если вы опасаетесь наихудшего случая.

Вот попытка в C. Это не помечено как домашнее задание.

// Assumes a sorted integer array with no duplicates
void printMatching(int array[], int size, int sum)
{
   int i = 0, k = size - 1;
   int curSum;
   while(i < k)
   {
      curSum = array[i] + array[k];
      if(curSum == sum)
      {
         printf("Found match at indices %d, %d\n", i, k);
         i++;k--;
      }
      else if(curSum < sum)
      {
         i++;
      }
      else
      {
         k--;
      }
   }
}

Вот тестовый результат с использованием int a [] = {3, 5, 6, 7, 8, 9, 13, 15, 17};

Searching for 12..
Found match at indices 0, 5
Found match at indices 1, 3
Searching for 22...
Found match at indices 1, 8
Found match at indices 3, 7
Found match at indices 5, 6
Searching for 4..
Searching for 50..

Поиск линейный, поэтому O (n) . Сортировка, которая происходит за кулисами, будет O (n * logn), если вы используете одну из хороших сортировок.

Из-за математики, лежащей в основе Big-O, меньший член в аддитивных терминах будет фактически исключен из ваших вычислений, и вы получите O (n logn).

Это можно сделать за O (n) , используя хеш-таблицу. Инициализируйте таблицу всеми числами в массиве, используя число в качестве ключа и частоту в качестве значения. Просмотрите каждое число в массиве и посмотрите, существует ли (сумма - число) в таблице. Если это так, у вас есть совпадение. После того, как вы перебрали все числа в массиве, у вас должен быть список всех пар, которые в сумме дают желаемое число.

array = initial array
table = hash(array)
S = sum

for each n in array
    if table[S-n] exists
        print "found numbers" n, S-n

Случай, когда n и таблица [S-n] ссылаются на одно и то же число дважды, может быть обработан дополнительной проверкой, но сложность остается O (n) .

def sum_in(numbers, sum_):
    """whether any two numbers from `numbers` form `sum_`."""
    a = set(numbers) # O(n)
    return any((sum_ - n) in a for n in a) # O(n)

Пример:

>>> sum_in([200, -10, -100], 100)
True