Zwei-Zeiger-Technik
Zwei Zeiger sind wirklich eine einfache und effektive Technik, die normalerweise zum Suchen von Paaren in einem sortierten Array verwendet wird.
Gegeben sei ein sortiertes Array A (in aufsteigender Reihenfolge sortiert) mit N ganzen Zahlen, finde heraus, ob es irgendein Paar von Elementen (A[i], A[j]) gibt, so dass ihre Summe gleich X ist.
Abbildung:
A[] = {10, 20, 35, 50, 75, 80}
X = =70
i = 0
j - 5
A[i] + A[j] = 10 + 80 = 90
Since A[i] + A[j] > X, j--
i = 0
j = 4
A[i] + A[j] = 10 + 75 = 85
Since A[i] + A[j] > X, j--
i = 0
j = 3
A[i] + A[j] = 10 + 50 = 60
Since A[i] + A[j] < X, i++
i = 1
j = 3
m
A[i] + A[j] = 20 + 50 = 70
Thus this signifies that Pair is Found.
Lassen Sie uns kurz die Funktionsweise des Zwei-Zeiger-Algorithmus diskutieren, der wie folgt ist. Der Algorithmus nutzt im Wesentlichen die Tatsache, dass das Eingabearray sortiert ist. Wir beginnen mit der Summe der Extremwerte (kleinster und größter) und bewegen bedingt beide Zeiger. Wir bewegen den linken Zeiger 'i', wenn die Summe von A[i] und A[j] kleiner als X ist. Wir verpassen kein Paar, da die Summe bereits kleiner als X ist. Dieselbe Logik gilt für den rechten Zeiger j.
Methoden:
Hier werden wir einen Zwei-Zeiger-Algorithmus vorschlagen, indem wir mit dem naiven Ansatz beginnen, nur um die Ausführung von Operationen zu demonstrieren, die in beiden Methoden ablaufen, und sekundär zu rechtfertigen, wie der Zwei-Zeiger-Algorithmus Code über Zeitkomplexitäten in allen dynamischen Programmiersprachen optimiert wie C+, Java, Python und sogar JavaScript
- Naiver Ansatz mit Schleifen
- Optimaler Ansatz mit Zwei-Zeiger-Algorithmus
Implementierung:
Methode 1: Naiver Ansatz
Beispiele
C++
// C++ Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
// Importing all libraries
#include <bits/stdc++.h>
using namespace std;
bool isPairSum(int A[], int N, int X)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
// as equal i and j means same element
if (i == j)
continue;
// pair exists
if (A[i] + A[j] == X)
return true;
// as the array is sorted
if (A[i] + A[j] > X)
break;
}
}
// No pair found with given sum.
return false;
}
// Driver code
int main()
{
int arr[] = { 3, 5, 9, 2, 8, 10, 11 };
int val = 17;
int arrSize = *(&arr + 1) - arr;
sort(arr, arr + arrSize); // Sort the array
// Function call
cout << isPairSum(arr, arrSize, val);
return 0;
}
C
// C Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
// Importing all libraries
#include <stdio.h>
int isPairSum(int A[],int N,int X)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
{
// as equal i and j means same element
if (i == j)
continue;
// pair exists
if (A[i] + A[j] == X)
return true;
// as the array is sorted
if (A[i] + A[j] > X)
break;
}
}
// No pair found with given sum.
return 0;
}
// Driver Code
int main()
{
int arr[]={3,5,9,2,8,10,11};
int val=17;
int arrSize = sizeof(arr)/sizeof(arr[0]);
// Function call
printf("%d",isPairSum(arr,arrSize,val));
return 0;
}
Java
// Java Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
// Importig all input output classes
import java.io.*;
// Main class
class GFG {
// Method 1
// Main driver method
public static void main(String[] args)
{
// Declaring and initializing array
int arr[] = { 3, 5, 9, 2, 8, 10, 11 };
int val = 17;
System.out.println(isPairSum(arr, arr.length, val));
}
// Method 2
// To find Pairs in A[0..N-1] with given sum
private static int isPairSum(int A[], int N, int X)
{
// Nested for loops for iterations
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
// As equal i and j means same element
if (i == j)
// continue keyword skips the execution
// for following condition
continue;
// Condition check if pair exists
if (A[i] + A[j] == X)
return 1;
// By now the array is sorted
if (A[i] + A[j] > X)
// Break keyword to hault the execution
break;
}
}
// No pair found with given sum.
return 0;
}
}
Python3
# Python Program Illustrating Naive Approach to # Find if There is a Pair in A[0..N-1] with Given Sum # Method def isPairSum(A, N, X): for i in range(N): for j in range(N): # as equal i and j means same element if(i == j): continue # pair exists if (A[i] + A[j] == X): return True # as the array is sorted if (A[i] + A[j] > X): break # No pair found with given sum return 0 # Driver code arr = [3, 5, 9, 2, 8, 10, 11] val = 17 print(isPairSum(arr, len(arr), val)) # This code is contributed by maheshwaripiyush9
C#
// C# Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
using System;
// Main class
class GFG {
// Method 1
// Main driver method
public static void Main(String[] args)
{
// Declaring and initializing array
int []arr = { 3, 5, 9, 2, 8, 10, 11 };
int val = 17;
Console.Write(isPairSum(arr, arr.Length, val));
}
// Method 2
// To find Pairs in A[0..N-1] with given sum
private static int isPairSum(int []A, int N, int X)
{
// Nested for loops for iterations
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// As equal i and j means same element
if (i == j)
// continue keyword skips the execution
// for following condition
continue;
// Condition check if pair exists
if (A[i] + A[j] == X)
return 1;
// By now the array is sorted
if (A[i] + A[j] > X)
// Break keyword to hault the execution
break;
}
}
// No pair found with given sum.
return 0;
}
}
// This code is contributed by shivanisinghss2110
Javascript
// JavaScript Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
<script>
// Naive solution to find if there is a
// pair in A[0..N-1] with given sum.
function isPairSum(A, N, X)
{
for (var i = 0; i < N-1; i++)
{
for (var j = i+1; j < N; j++)
{
// as equal i and j means same element
if (i == j)
continue;
// pair exists
if (A[i] + A[j] == X)
return 1;
// as the array is sorted
if (A[i] + A[j] > X)
break;
}
}
// No pair found with given sum.
return 0;
}
var arr=[ 3, 5, 9, 2, 8, 10, 11 ];
// value to search
var val = 17;
// size of the array
var arrSize = 7;
// Function call
document.write(isPairSum(arr, arrSize, val));
</script>
Ausgabe
1
Zeitkomplexität: O(n 2 ).
Methode 2: Zwei-Zeiger-Technik
Sehen wir uns nun an, wie die Zwei-Zeiger-Technik funktioniert. Wir nehmen zwei Zeiger, von denen einer das erste Element und der andere das letzte Element des Arrays darstellt, und addieren dann die Werte, die an beiden Zeigern gespeichert sind. Wenn ihre Summe kleiner als X ist, verschieben wir den linken Zeiger nach rechts oder wenn ihre Summe größer als X ist, verschieben wir den rechten Zeiger nach links, um näher an die Summe heranzukommen. Wir bewegen die Zeiger weiter, bis wir die Summe als X erhalten.
Beispiele
C++
// C++ Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
// Using Two-pointers Technique
// Importing required libraries
#include <iostream>
using namespace std;
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
int isPairSum(int A[], int N, int X)
{
// represents first pointer
int i = 0;
// represents second pointer
int j = N - 1;
while (i < j) {
// If we find a pair
if (A[i] + A[j] == X)
return 1;
// If sum of elements at current
// pointers is less, we move towards
// higher values by doing i++
else if (A[i] + A[j] < X)
i++;
// If sum of elements at current
// pointers is more, we move towards
// lower values by doing j--
else
j--;
}
return 0;
}
// Driver code
int main()
{
// array declaration
int arr[] = { 3, 5, 9, 2, 8, 10, 11 };
// value to search
int val = 17;
// size of the array
int arrSize = *(&arr + 1) - arr;
// Function call
cout << (bool)isPairSum(arr, arrSize, val);
return 0;
}
C
// C Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
// Using Two-pointers Technique
// Importing I/O libraries
#include <stdio.h>
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
int isPairSum(int A[], int N, int X)
{
// Represents first pointer
int i = 0;
// Represents second pointer
int j = N - 1;
while (i < j)
{
// If we find a pair
if (A[i] + A[j] == X)
return 1;
// If sum of elements at current
// pointers is less, we move towards
// higher values by doing i++
else if (A[i] + A[j] < X)
i++;
// If sum of elements at current
// pointers is more, we move towards
// lower values by doing j--
else
j--;
}
return 0;
}
// Main method
int main()
{
// Array declaration
int arr[] = { 3, 5, 9, 2, 8, 10, 11 };
// Custom value to be searched
int val = 17;
// size of the array
int arrSize = sizeof(arr) / sizeof(arr[0]);
// Function call
printf("%d", isPairSum(arr, arrSize, val));
return 0;
}
Java
// Java Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
// Using Two-pointers Technique
// Importing all utility classes
import java.io.*;
// Main class
class GFG
{
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
public static int isPairSum(int A[], int N, int X)
{
// represents first pointer
int i = 0;
// represents second pointer
int j = N - 1;
while (i < j) {
// If we find a pair
if (A[i] + A[j] == X)
return 1;
// If sum of elements at current
// pointers is less, we move towards
// higher values by doing i++
else if (A[i] + A[j] < X)
i++;
// If sum of elements at current
// pointers is more, we move towards
// lower values by doing j--
else
j--;
}
return 0;
}
// Driver code
public static void main(String[] args)
{
// array declaration
int arr[] = { 3, 5, 9, 2, 8, 10, 11 };
// value to search
int val = 17;
// size of the array
int arrSize = arr.length;
// Function call
System.out.println(isPairSum(arr, arrSize, val));
}
}
Python3
# Java Program Illustrating Naive Approach to # Find if There is a Pair in A[0..N-1] with Given Sum # Using Two-pointers Technique # Method def isPairSum(A, N, X): # represents first pointer i = 0 # represents second pointer j = N - 1 while(i < j): # If we find a pair if (A[i] + A[j] == X): return True # If sum of elements at current # pointers is less, we move towards # higher values by doing i += 1 elif(A[i] + A[j] < X): i += 1 # If sum of elements at current # pointers is more, we move towards # lower values by doing j -= 1 else: j -= 1 return 0 # array declaration arr = [3, 5, 9, 2, 8, 10, 11] # value to search val = 17 print(isPairSum(arr, len(arr), val)) # This code is contributed by maheshwaripiyush9.
C#
// C# Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
// Using Two-pointers Technique
// Importing all utility classes
using System;
// Main class
class GFG
{
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
public static int isPairSum(int []A, int N, int X)
{
// represents first pointer
int i = 0;
// represents second pointer
int j = N - 1;
while (i < j) {
// If we find a pair
if (A[i] + A[j] == X)
return 1;
// If sum of elements at current
// pointers is less, we move towards
// higher values by doing i++
else if (A[i] + A[j] < X)
i++;
// If sum of elements at current
// pointers is more, we move towards
// lower values by doing j--
else
j--;
}
return 0;
}
// Driver code
public static void Main(String[] args)
{
// array declaration
int []arr = { 3, 5, 9, 2, 8, 10, 11 };
// value to search
int val = 17;
// size of the array
int arrSize = arr.Length;
// Function call
Console.Write(isPairSum(arr, arrSize, val));
}
}
// This code is contributed by shivanisinghss2110
Javascript
// JavaScript Program Illustrating Naive Approach to
// Find if There is a Pair in A[0..N-1] with Given Sum
// Using Two-pointers Technique
<script>
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
function isPairSum(A, N, X)
{
// represents first pointer
var i = 0;
// represents second pointer
var j = N - 1;
while (i < j) {
// If we find a pair
if (A[i] + A[j] == X)
return true;
// If sum of elements at current
// pointers is less, we move towards
// higher values by doing i++
else if (A[i] + A[j] < X)
i++;
// If sum of elements at current
// pointers is more, we move towards
// lower values by doing j--
else
j--;
}
return false;
}
// Driver code
// array declaration
var arr = [ 3, 5, 9, 2, 8, 10, 11 ];
// value to search
var val = 17;
// size of the array
var arrSize =7;
// Function call
document.write(isPairSum(arr, arrSize, val));
// This Code is Contributed by Harshit Srivastava
</script>
Ausgabe
1
Zeitkomplexität: O(n)
Weitere Probleme basierend auf der Zwei-Zeiger-Technik.
- Finden Sie das nächste Paar aus zwei sortierten Arrays
- Finden Sie das Paar im Array, dessen Summe x am nächsten ist
- Finden Sie alle Drillinge mit Nullsumme
- Finden Sie ein Triplett, dessen Summe einen gegebenen Wert ergibt
- Finden Sie ein Triplett, bei dem die Summe von zwei dem dritten Element entspricht
- Finden Sie vier Elemente, deren Summe einen bestimmten Wert ergibt
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .