Trouvez toutes les paires de n qui se résument à S

Donné un tableau, trouver toutes les paires de la nsa, qui aboutissent à une valeur donnée.
Il y a le classique algorithme O(n) de garder les 2 pointeurs à l'avant et à l'arrière et les rapprocher pour trouver la paire. Cela ne mène qu'à 1 paire. Si vous voulez toutes les paires.
Bonus: Trouver le minimum de la distance de la paire.

Pouvez-vous faire cela en O(n).

source d'informationauteur shreyasva

  1. 9
     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. 3

    Un seul et même (temps) solution efficace implique un hachage de la carte à partir des entiers les nombres entiers. Cet algorithme fonctionne en parcourant le tableau. Sur chaque élément x, de rechercher somme - x dans la table de hachage et, si elle existe, print (x, somme - x). Ajouter x à la table de hachage, et aller à l'élément suivant.

    Mais pour O(1) de la constante de l'espace et de O(n) en temps linéaire sur tableau trié,code ci-dessous sûrement œuvres.

    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. 2
    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. 0

    Source Lien

    Vecteur de bits:

    Je l'aime. Avoir un vecteur de bits (j'.e.tableau de bits) de taille égale à la somme totale.

    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]

    Ce sera ont besoin constant de stockage O(n) et le temps de la complexité est O(n) dans tous les cas.

  5. 0

    Peu de modification à coder_15 réponse, pour vérifier si l'élément suivant de premier est le même que le premier ou l'élément précédent, pour la dernière est la même que la dernière: 

    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;
    }
}