This is the 5th day of my participation in the August More Text Challenge

Requirements:

Experimental process:

One, exhaustive method

The time complexity at this time is O (n2).

#include<iostream>
using namespace std;

const int n=5;

/ / the exhaustive method
bool find(int a[],int n,int S){
for(int i=0; i<n; i++){for(int j=i+1; j<n; j++){// Note that j= I +1 instead of j= I
            if((a[i]+a[j])==S)
            return true; }}return false;
}

int main(a){
    int a[n];
    cout<<"Please enter length as"<<n<<Each element in the array of:<<endl;
    for(int i=0; i<n; i++){ cin>>a[i]; }int S;
    cout<<"Target value is:"<<endl;
    cin>>S;
    if(find(a,n,S)==true){
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    system("PAUSE");
    return 0;
}
Copy the code

First, sort the array

Basic idea:

First sort the array in quicksort order from smallest to largest, then define two Pointers I and j, I from left to right and j from right to left. Like this:

(1) If data[I]+data[j]<target, then ++ I;

(2) if data[I]+data[j]>target, –j;

Data [I]+data[j]=target;

If I >=j, return false.

#include<iostream>
using namespace std;

const int n=5;

/ / fast row
int Partition(int p[],int left,int right){
    int pivot=p[left];
    while(left<right){
        while(left<right&&p[right]>=pivot) right--;
        p[left]=p[right];
        while(left<right&&p[left]<=pivot) left++;
        p[right]=p[left];
    }
    p[left]=pivot;
    return left;
}

void QuickSort(int p[],int left,int right){
    if(left<right){
        int q=Partition(p,left,right);
        QuickSort(p,left,q- 1);
        QuickSort(p,q+1,right); }}bool find(int data[],int left,int right,int target)
{
    int i=left,j=right;
    while(i<j){
        if(data[i]+data[j]==target&&i<j)
        return true;
        else if(data[i]+data[j]<target&&i<j)
        ++i;
        else if(data[i]+data[j]>target&&i<j) 
        --j;    
    }
    return false;
}


int main(a){
    int a[n];
    cout<<"Please enter length as"<<n<<Each element in the array of:<<endl;
    for(int i=0; i<n; i++){ cin>>a[i]; }int S;
    cout<<"Target value is:"<<endl;
    cin>>S;
    QuickSort(a,0,n- 1);
    if(find(a,0,n- 1,S)==true)
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl; 
    system("PAUSE");
    return 0;
}
Copy the code

At this time, the sorting time complexity is O (nlogn), and the traversal complexity between the two Pointers is O (n), so the total time complexity is O (nlogn).