【数据结构与算法】十三 twoSum hash

Bertha 。 2022-07-28 01:37 128阅读 0赞

# **【数据结构与算法】十三 twoSum hash** #

# **无序数组两数和等于目标** #

C++

#include <stdio.h>
    #include <iostream>
    
    using namespace std ;
    
    template <class T>
    int getArrayLen(const T& array){
        return sizeof(array) / sizeof(array[0]) ;
    }
    
    template <class T>
    void twoSum(int target , T & array){
        int len = getArrayLen(array) ;
        for(int i=0;i<len;i++){
            for( int j=i+1;j<len;j++){
                if(array[i] + array[j] == target){
                    cout << "found " << array[i] << " , " << array[j] << endl;
                }
            }
        }
        cout << endl;
    }
    
    int main(){
        int target = 10 ;
    
        int a1[] = {
        0,1,2,3,4,5,6,7,8,9};
        twoSum(target , a1);
    
        int a2[] = {
        5,6,7,8,9,0,1,2,3,4};
        twoSum(target , a2);
    
        return 0;
    }

以上是双重循环，很容易想到，但是效率问题，下面来优化

# **时间复杂度** #

O(n2)

--------------------

# **排序后求和** #

C++

#include <stdio.h>
    #include <iostream>
    #include <algorithm>
    
    using namespace std ;
    
    template <class T>
    int getArrayLen(const T& array){
        return sizeof(array) / sizeof(array[0]) ;
    }
    
    template <class T>
    void twoSum(int target , T & array){
        int len = getArrayLen(array) ;
        int left = 0 ;
        int right = len - 1;
    
    
        while( left < right ){
            if(array[left] + array[right] == target){
                cout << "found " << array[left] << " , " << array[right] << endl;
                left ++ ; right -- ;
            }else if(array[left] + array[right] < target)
                left ++;
            else
                right --;
        }
        cout << endl;
    }
    
    int main(){
    
        int target = 9 ;
    
        int a1[] = {
        0,1,7,8,9,2,3,4,5,6};
        sort(a1, a1 + 10);
        twoSum(target , a1);
    
        int a2[] = {
        5,6,7,8,9,0,1,2,3,4};
        sort(a2, a2 + 10);
        twoSum(target , a2);
    
        return 0;
    }

# **时间复杂度** #

O(nlogn)

--------------------

# **基于hash实现** #

C++

#include <stdio.h>
    #include "iostream"
    #include <unordered_set>
    
    using namespace std;
    
    
    template <class T>
    int getArrayLen(const T& array){
        return sizeof(array) / sizeof(array[0]) ;
    }
    
    template <class T>
    void twoSum(int target , T & array){
        unordered_set<int> hash_set;
        int len = getArrayLen(array);
        for(int i = 0; i < len; i++){
            if(hash_set.count(target - array[i])){
                cout << "Found:" << array[i] << "," << target-array[i] << endl;
            }
            hash_set.insert(array[i]);
        }
        cout << endl;
    }
    
    
    int main(){
        int target = 9;
        int a1[] = {
        0,1,7,8,9,2,3,4,5,6};
        int a2[] = {
        5,6,7,8,9,0,1,2,3,4};
    
        twoSum(target , a1);
        twoSum(target , a2);
    
        return 0;
    }

# **时间复杂度** #

O(n)

--------------------

JAVA

static void twoSum(int target , int array[]){
            int len = array.length;
            HashSet set = new HashSet();
            for(int i=0;i<len;i++){
                if(set.contains( target - array[i] ) )
                    System.out.println("fond : " + array[i] + " , " + (target - array[i]) );
                set.add(array[i]);
            }
        }
    
        public static void main(String[] args) {
            int target = 9;
            int a1[] = {
       3,7,0,1,2,8,9,4,5,6};
            twoSum(target , a1);
            System.out.println();
            int a2[] = {
       1,2,8,9,4,5,6,3,7,0};
            twoSum(target , a2);
        }

# **时间复杂度** #

O(n)

--------------------