இரண்டு தொகை லீட்கோட் தீர்வு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது ஆப்பிள் ByteDance intuit மைக்ரோசாப்ட் ஆரக்கிள்
பைனரி தேடல் குறியீட்டு பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions இரண்டு சுட்டிக்காட்டி

இந்த சிக்கலில், a இல் இரண்டு தனித்துவமான குறியீடுகளின் ஜோடியைக் கண்டுபிடிக்க வேண்டும் வரிசைப்படுத்தப்பட்ட வரிசை அவற்றின் மதிப்புகள் கொடுக்கப்பட்ட இலக்கைச் சேர்க்கின்றன. வரிசைக்கு மட்டுமே உள்ளது என்று நாம் கருதலாம் ஒரு இலக்கு தொகையைச் சேர்க்கும் முழு எண்களின் ஜோடி. வரிசை a இல் வரிசைப்படுத்தப்பட்டுள்ளது என்பதை நினைவில் கொள்க குறையாத முறையில்.

உதாரணமாக  

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 = வரிசையின் அளவு. சாத்தியமான ஜோடியை நாங்கள் சரிபார்க்கும்போது, ​​மொத்த ஜோடிகளின் எண்ணிக்கை: N * (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). மாறிகளுக்கு நிலையான இடத்தைப் பயன்படுத்துகிறோம்.