BM50 两数之和

主要思想：快速排序+二分查找

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int binary_search( std::vector<std::pair<int,int>>& table,int left,int right,int t){
        int ret=-1;
        while(left<=right){
            int mid=(left+right)/2;
            const std::pair<int,int>& key=table.at(mid);
            if(t==key.first){
                return key.second;
            }else if(key.first<t){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return ret;
    }
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        int n=numbers.size();
        std::vector<std::pair<int,int>> table;
        for(int i=0;i<n;i++){
            int v=numbers.at(i);
            table.push_back(std::make_pair(v,i+1));
        }
        std::sort(table.begin(),table.end(),[](const std::pair<int,int> &a,
                                               const std::pair<int,int> &b){
                        return a.first<b.first;
                  });
        std::vector<int> ret;
        for(int i=0;i<n;i++){
            const std::pair<int,int>& key_a=table.at(i);
            int b=target-key_a.first;
            int index=binary_search(table,i+1,n-1,b);
            if(index>=0){
                if(index>key_a.second){
                    ret.push_back(key_a.second);
                    ret.push_back(index);
                }else{
                    ret.push_back(index);
                    ret.push_back(key_a.second);
                }
                break;
            }
        }
        return ret;
    }
};
int main(){
    std::vector<int> nums={2,1,9,4,4,56,90,3};
    Solution su;
    std::vector<int> ret;
    ret=su.twoSum(nums,8);
    std::cout<<ret.at(0)<<" "<<ret.at(1)<<std::endl;
    return 0;
}

[1]BM50 两数之和