3_两数之和: 双指针/字典

「爱情、让人受尽委屈。」 2023-01-07 07:10 85阅读 0赞

# 问题介绍 #

*  167.Two Sum II - Input array is sorted
 *  描述: 在一个增序的整数数组里找到两个数，使它们的和为给定值。已知有且只有一对解。

Input: numbers = [2,7,11,15], target = 9
    Output: [1,2]

总结: 这题太重要了, 包含两种重要算法的思想,

*  a. 利用双指针对有序数列前后相加与目标值比较, 通过向中间移动两个指针最终得到目标值, 死亡条件是两个指针重叠, 表示没有找到目标
 *  b. 利用字典从头遍历,key=number, value=item, 如果target-numbers\[item\] in map.keys, 则找到的numbers\[ map\[target-numbers\[item\]\] \] 与 numbers\[item\]就是结果

# 一. 解题 #

#include<iostream>
    #include<algorithm>
    #include<vector>
    #include<stdio.h>
    #include <map>
    
    using namespace std;
    void print_vector(vector<int> numbers){ 
        for(auto c : numbers) cout<< c <<" ";cout<<endl;
    }
    
    // 使用&, 指的是函数参数传递进来的可以被改变,引用传递, int a, func(a) func(int &a){a=100}
    // 使用*, 指的是参数即为指针, int a, func(&a) func(int *a){*a=100}
    int solution1(vector<int> numbers, int target){ 
        print_vector(numbers);
        sort(numbers.begin(), numbers.end());
        int sum, i=0,j=numbers.size()-1;
        while (i<j){ 
            sum= numbers[i]+numbers[j];
            if (sum>target) { j--; }
            else if(sum==target) { break; }
            else { i++;}
        }
        print_vector(numbers);
        printf("%d = %d+%d\n", target, numbers[i], numbers[j]);
    }
    
    // 也可以做一个字典, 字典只需要遍历一遍即可, 不需要排序, 而双指针需要排序, 相当于遍历两遍
    void solution2(vector<int> numbers, int target){ 
        map<int,int> personnel;
        for(int i=0; i<numbers.size(); i++){ 
            int sum = target-numbers[i];
            if (personnel.find(sum) == personnel.end()){ 
                personnel.insert(pair<int, int>(numbers[i],i));
            }else{ 
                printf("%d = %d+%d\n", target, numbers[i], personnel.find(sum)->first);
            }
        }
    }
    // python解法
    // numbers = [1,2,4,5,7]
    // target = 9
    
    // map1 = {}
    // for i,numb in enumerate(numbers):
    // if map1.get(target-numb)==None:
    // map1[numb] = i
    // else:
    // print(numb, target-numb)
    
    
    int main(int argc, char const *argv[])
    { 
        vector<int>numbers = { 2,7,11,15,1,2};
    
        result(numbers, 9);
        solution1(numbers, 9);
        cout<<"hello" <<endl;
        return 0;
    }