ਦੋ ਜੋੜ ਲੀਟਕੋਡ ਹੱਲ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਸੇਬ ਬਾਈਟਡੈਂਸ Intuit Microsoft ਦੇ ਓਰੇਕਲ
ਬਾਈਨਰੀ ਖੋਜ ਦੋ ਪੁਆਇੰਟਰ

ਇਸ ਸਮੱਸਿਆ ਵਿੱਚ, ਸਾਨੂੰ ਏ ਵਿੱਚ ਦੋ ਵੱਖਰੇ ਸੂਚਕਾਂਕ ਦੀ ਜੋੜੀ ਲੱਭਣੀ ਪਏਗੀ ਕ੍ਰਮਬੱਧ ਐਰੇ ਕਿ ਉਹਨਾਂ ਦੇ ਮੁੱਲ ਇੱਕ ਦਿੱਤੇ ਟੀਚੇ ਵਿੱਚ ਜੋੜਦੇ ਹਨ. ਅਸੀਂ ਮੰਨ ਸਕਦੇ ਹਾਂ ਕਿ ਐਰੇ ਕੋਲ ਹੀ ਹੈ ਇੱਕ ਪੂਰਨ ਅੰਕ ਦੀ ਜੋੜੀ ਜੋ ਟੀਚੇ ਦੀ ਰਕਮ ਨੂੰ ਜੋੜਦੀ ਹੈ. ਧਿਆਨ ਦਿਓ ਕਿ ਐਰੇ ਨੂੰ ਕ੍ਰਮਬੱਧ ਕੀਤਾ ਗਿਆ ਹੈ ਗੈਰ-ਘਟ ਤਰੀਕੇ ਨਾਲ

ਉਦਾਹਰਨ

Array = {1 , 2 , 3 , 4 , 5}
Target = 6
1 5
Array = {1 , 4 , 5 , 11 , 12}
Target = 9
2 3

ਪਹੁੰਚ (ਬਰੂਟ ਫੋਰਸ)

ਇਹ ਪਹੁੰਚ ਸਿੱਧੀ ਹੈ. ਅਸੀਂ ਐਰੇ ਵਿਚਲੀ ਹਰ ਜੋੜੀ ਦੀ ਜਾਂਚ ਕਰ ਸਕਦੇ ਹਾਂ ਅਤੇ ਜੇ ਉਨ੍ਹਾਂ ਦੀ ਰਕਮ ਦਿੱਤੇ ਟੀਚੇ ਦੇ ਬਰਾਬਰ ਹੈ, ਤਾਂ ਉਹਨਾਂ ਦੇ ਸੂਚਕਾਂਕ ਛਾਪੋ. ਇਸ ਕਿਸਮ ਦੀ ਬਰੂਟ ਫੋਰਸ ਹੱਲ ਨੂੰ ਐਰੇ = ਵਿੱਚ ਹਰ ਸੰਭਵ ਜੋੜੀ ਅਤੇ ਸੰਭਵ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ ਦੀ ਜਾਂਚ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ n * (n - 1) / 2. ਇਸ ਲਈ, ਸਭ ਤੋਂ ਬੁਰੀ ਸਥਿਤੀ ਵਿੱਚ, ਇਹ ਪਹੁੰਚ ਹੌਲੀ ਹੋ ਸਕਦੀ ਹੈ.

ਐਲਗੋਰਿਥਮ

  1. ਐਰੇ ਵਿਚ ਘੋਲ ਦਾ ਪਹਿਲਾ ਇੰਡੈਕਸ ਬਰਕਰਾਰ ਰੱਖਣ ਲਈ ਇਕ ਲੂਪ ਚਲਾਓ
  2. ਹਰ ਪਹਿਲੇ ਪੂਰਨ ਅੰਕ ਲਈ ਹੱਲ ਦਾ ਦੂਜਾ ਸੂਚਕਾਂਕ ਬਣਾਈ ਰੱਖਣ ਲਈ ਇਕ ਹੋਰ ਲੂਪ ਚਲਾਓ
  3. ਜੇ ਕਿਸੇ ਵੀ ਸਮੇਂ, ਦੋ ਸੂਚਕਾਂਕ ਦੇ ਮੁੱਲਾਂ ਦਾ ਜੋੜ ਟੀਚੇ ਦੇ ਬਰਾਬਰ ਹੁੰਦਾ ਹੈ
    • ਇਸਦੇ ਸੂਚਕਾਂਕ ਛਾਪੋ

ਦੋ ਜੋੜ ਲੀਟਕੋਡ ਹੱਲ਼ ਦਾ ਅਮਲ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#include <bits/stdc++.h>
using namespace std;

vector <int> targetSum(vector <int> &a , int &target)
{
    int n = a.size();
    for(int i = 0 ; i < n - 1 ; i++)
        for(int j = i + 1 ; j < n ; j++)
        {
            if(a[i] + a[j] == target)
                return {i + 1 , j + 1};
        }
    return {};
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 11 , 12};
    int target = 9;
    for(int &x : targetSum(a , target))
        cout << x << " ";
    cout << '\n';
}

ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ

class target_sum
{
    static int[] targetSum(int []a , int target)
    {
        for(int i = 0 ; i < a.length - 1 ; i++)
            for(int j = i + 1 ; j < a.length ; j++)
            {
                if(a[i] + a[j] == target)
                    return new int[]{i + 1 , j + 1};
            }
        return new int[]{-1 , -1};
    }


    public static void main(String args[])
    {
        int [] a = {1 , 4 , 5 , 11 , 12};
        int target = 9;

        for(int x : targetSum(a , target))
            System.out.print(x + " ");
    }
}
2 3

ਦੋ ਜੋੜ ਲੀਟਕੋਡ ਹੱਲ ਦਾ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ * ਐਨ), ਜਿੱਥੇ N = ਐਰੇ ਦਾ ਆਕਾਰ. ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਸੰਭਵ ਜੋੜੀ ਦੀ ਜਾਂਚ ਕਰਦੇ ਹਾਂ, ਅਤੇ ਜੋੜਿਆਂ ਦੀ ਕੁੱਲ ਸੰਖਿਆ: ਐਨ * (ਐਨ - 1) / 2.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1). ਵੇਰੀਏਬਲ ਲਈ ਸਿਰਫ ਨਿਰੰਤਰ ਜਗ੍ਹਾ ਵਰਤੀ ਜਾਂਦੀ ਹੈ.

ਪਹੁੰਚ (ਦੋ ਪੁਆਇੰਟਰ)

ਐਲਗੋਰਿਥਮ

ਦੇਣ ਐਰੇ ਹੈ ਕ੍ਰਮਬੱਧ ਇਹ ਇਕ ਵਿਸ਼ੇਸ਼ ਕੇਸ ਹੈ ਕਿਉਂਕਿ ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ ਜੇ ਅਸੀਂ ਪਹਿਲਾਂ ਸੂਚਕਾਂਕ ਨਿਰਧਾਰਤ ਕੀਤਾ ਹੈ ਤਾਂ ਟੀਚੇ ਨੂੰ ਪੂਰਾ ਕਰਨ ਲਈ ਲੋੜੀਂਦਾ ਮੁੱਲ ਐਰੇ ਵਿਚ ਅੱਗੇ ਪਾਏ ਜਾਣ ਦੀ ਵਰਤੋਂ ਕਰਕੇ. ਬਾਈਨਰੀ ਖੋਜ. 

ਇਕੋ ਜਿਹੀ ਪਹੁੰਚ ਵਰਤੀ ਜਾ ਸਕਦੀ ਹੈ: ਅਸੀਂ ਇਸਤੇਮਾਲ ਕਰ ਸਕਦੇ ਹਾਂ ਦੋ ਪੁਆਇੰਟਰ: ਖੱਬੇ ਅਤੇ ਦਾ ਹੱਕ, ਅਸਲ ਵਿੱਚ ਪਹਿਲੀ ਅਤੇ ਪਿਛਲੇ ਕ੍ਰਮਵਾਰ ਐਰੇ ਦਾ ਤੱਤ. ਫਿਰ ਅਸੀਂ ਇਨ੍ਹਾਂ ਦੋਵਾਂ ਪੁਆਇੰਟਰ ਮੁੱਲਾਂ ਦੀ ਤੁਲਨਾ ਟੀਚੇ ਨਾਲ ਕਰ ਸਕਦੇ ਹਾਂ. ਜੇ ਮੁੱਲ ਅਤੇ ਟੀਚੇ ਦਾ ਜੋੜ ਬਰਾਬਰ ਹੈ, ਤਾਂ ਅਸੀਂ ਲੱਭ ਲਿਆ ਹੈ ਸਿਰਫ ਦਾ ਹੱਲ. ਸੋ, ਅਸੀਂ ਇਸ ਇੰਡੈਕਸ ਜੋੜੀ ਨੂੰ ਵਾਪਸ ਕਰਦੇ ਹਾਂ. ਨਹੀਂ ਤਾਂ, ਜੇ ਮੁੱਲ ਦਾ ਜੋੜ ਹੈ ਘੱਟ ਟੀਚੇ ਦੀ ਬਜਾਏ, ਸਾਨੂੰ ਪੁਆਇੰਟਰਾਂ ਵਿਚੋਂ ਇਕ ਨੂੰ ਵਧਾਉਣ ਜਾਂ ਮੁੜ ਦੁਬਾਰਾ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਸਪੱਸ਼ਟ ਹੈ, ਅਸੀਂ ਲਿਆ ਰਹੇ ਹਾਂ ਸੱਜੇ ਸਿਰਫ ਸਿਰੇ ਤੋਂ ਪੁਆਇੰਟਰ. ਇਸ ਲਈ, ਸਾਨੂੰ ਵਧਾਉਣਾ ਚਾਹੀਦਾ ਹੈ ਨੂੰ ਛੱਡ ਪੁਆਇੰਟਰ ਅਤੇ ਉਸੇ ਸਥਿਤੀ ਦੀ ਜਾਂਚ ਕਰੋ. ਇਸੇ ਤਰ੍ਹਾਂ, ਜੇ ਮੁੱਲਾਂ ਦਾ ਜੋੜ ਟੀਚੇ ਤੋਂ ਵੱਧ ਹੁੰਦਾ ਹੈ, ਅਸੀਂ ਘਟਦੇ ਹਾਂ ਸੱਜੇ ਪੁਆਇੰਟਰ

ਇੱਕ ਕ੍ਰਮਬੱਧ ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨਜ਼ ਵਿੱਚ ਨਿਸ਼ਾਨਾ ਬਣਾਉਣ ਲਈ ਦੋ ਪੂਰਨ ਅੰਕ ਜੋੜ ਰਹੇ ਹਨ

ਦਾ ਅਮਲ ਦੋ ਜੋੜ ਲੀਟਕੋਡ ਹੱਲ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#include <bits/stdc++.h>
using namespace std;

vector <int> targetSum(vector <int> &a , int &target)
{
    int left = 0 , right = int(a.size()) - 1 , tempSum;
    while(left < right)
    {
        tempSum = a[left] + a[right];
        if(tempSum == target)
            return {left + 1 , right + 1};
        if(tempSum > target)
            right--;
        else
            left++;
    }
    return {-1 , -1};
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 11 , 12};
    int target = 9;
    for(int &x : targetSum(a , target))
        cout << x << " ";
    cout << '\n';
}

ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ

class target_sum
{
    static int[] targetSum(int []a , int target)
    {
        int left = 0 , right = a.length - 1 , tempSum;
        while(left < right)
        {
            tempSum = a[left] + a[right];
            if(tempSum == target)
                return new int[]{left + 1 , right + 1};
            if(tempSum > target)
                right--;
            else
                left++;
        }
        return new int[]{-1 , -1};
    }


    public static void main(String args[])
    {
        int [] a = {1 , 4 , 5 , 11 , 12};
        int target = 9;

        for(int x : targetSum(a , target))
            System.out.print(x + " ");
    }
}
2 3

ਦੋ ਜੋੜ ਲੀਟਕੋਡ ਹੱਲ ਦਾ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਜਿਵੇਂ ਕਿ ਸਭ ਤੋਂ ਮਾੜੇ ਹਾਲਾਤ ਵਿੱਚ ਵੀ, ਅਸੀਂ ਐਰੇ ਵਿਚਲੇ ਸਾਰੇ ਤੱਤਾਂ ਨੂੰ ਸਿਰਫ ਇਕ ਵਾਰ ਵੇਖਦੇ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1). ਅਸੀਂ ਵੇਰੀਏਬਲਸ ਲਈ ਨਿਰੰਤਰ ਜਗ੍ਹਾ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ.