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

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

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

Ответ 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 */

Ответ 2

Одно простое (время) эффективное решение включает хэш-карту от целых чисел до целых чисел. Этот алгоритм работает путем итерации через массив. На каждом элементе 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;
        }
    }
 }

Ответ 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);
    }

Ответ 4

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

Бит-вектор:

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

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) в любом случае.

Ответ 5

Небольшая поправка к запросу 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;
    }
}