Найти все пары номеров, которые составляют до S

Question

Для данного массива найдите все пары nos, которые суммируют до заданного значения.Существует классический алгоритм O (n) - держать 2 указателя спереди и сзади и сближать их, чтобы найти пару.Это приводит только к 1 паре.Что делать, если вы хотите, чтобы все пары.Бонус: найдите минимальную пару расстояний.

Можете ли вы сделать это в O (n).

Answer 1

 int arr[SIZE]; /* sorted in ascending order */

 int a = 0, b = SIZE - 1, mindist = -1, sum;
 while (a < b) {
    sum = arr[a] + arr[b];
    if (sum == TARGET) { report_pair(a, b); mindist = b - a; a++ }
    else if (sum < TARGET) a++;
    else b--;
 }

 /* minimum distance stored in mindist */

Answer 2

Одно простое и (время) эффективное решение включает в себя хэш-карту от целых чисел до целых чисел.Этот алгоритм работает путем перебора массива.Для каждого элемента x найдите sum - x в хэш-таблице и, если он существует, выведите (x, sum - x).Добавьте x в хеш-таблицу и перейдите к следующему элементу.

Но для O (1) постоянного пространства и O (n) линейного времени в отсортированном массиве приведенный ниже код наверняка работает.

public static void printPairSums(int[] array, int sum) {
    Arrays.sort(array);
    int first = 0;
    int last = array.length - 1;
    while (first < last) {
        int s = array[first] + array[last];
        if (s == sum) {
            System.out.println(array[first] + “ “ + array[last]);
            ++first;
            --last;
        } else {
            if (s < sum) ++first;
            else --last;
        }
    }
 }

Answer 3

public static void main(String[] args) {
        int[] nums = new int[] { 1,2,3,4,5,6,7,8,9};
        Hashtable  reqNoList=new Hashtable();
        int sum=6;
        int minPair=0,i=0,count=0;
        // just remove the second condition for unsorted array
        while(i<nums.length && i<sum){
            int key=sum-nums[i];
            if(reqNoList.containsKey(nums[i])){
                Integer temp=(Integer) reqNoList.get(nums[i]);
                System.out.println("("+key+","+nums[i]+")");
                if(count==0)
                    minPair=i-temp;
                else if((i-temp)< minPair)
                    minPair=i-temp;
                count++;
            }else
                reqNoList.put(key,i);
            i++;
        }
        System.out.println("min Distance -->"+minPair);
    }

Answer 4

Небольшая поправка к ответу coder_15, чтобы проверить, совпадает ли следующий элемент первым с первым или предыдущий элемент последним с последним:

while(first<last){
    int s = arr[first] + arr[last];
    if(s == sum){
        System.out.println(arr[first] + " : " + arr[last]);
        if(arr[first] == arr[first+1] ){
            System.out.println(arr[first+1] + " : " + arr[last]);
        }
        if(arr[last] == arr[last-1] ){
            System.out.println(arr[first] + " : " + arr[last-1]);
        }
        ++first; 
        --last; 
    }

    else{
        if(s<sum){
            ++first; 
        }
        if(s>sum)
            --last;
    }
}

Answer 5

Источник Ссылка

Битовый вектор:

Мне нравится этот. Иметь битовый вектор (то есть массив битов) размера, равного общей сумме.

1.clear all bits
2.for each element a[i] in the array
  - if bit sum-a[i] is set, return sum-a[i], a[i]
  - else, set bit a[i]

Для этого потребуется постоянная память O (n), а сложность по времени в любом случае равна O (n).