(leetcode)two sum的拓展

problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.(Input array is already sorted in ascending order.)

Solution:

• Binary search(O(nlogn) runtime, O(1)space)

C++:

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <iostream>
using namespace std;

class Solution 
{
public:
    vector<int> static twoSum(vector<int>& nums, int target) 
    {
        vector<int> id;
        int i, j;
        for (i = 0; i < nums.size(); i++) {
            j = bisearch(nums, target-nums[i], i+1);
            if (j != -1) {
                id.push_back(i);
                id.push_back(j);
                return id;
            }
        }
        
        return id = { -1,-1 };
        
    }
    static int bisearch(vector<int>& nums, int target, int start) {   //在nums中从start开始寻找target
        int i = start,j = nums.size()-1,m;
        while (i < j) {
            m = (i + j) / 2;
            if (nums[m] < target) i = m + 1;
            else j = m;
        }
        return (i == j&&nums[i] == target) ? i : -1;
    }
};


int main(void)
{
    int n , target = 0;
    cin >> n;
    vector<int> nums(n);
    vector<int> id;
    for (int i = 0; i < nums.size(); i++) {
        cin >> nums[i];
    }
    cout << "Input your target:" << endl;
    cin >> target;
    id = Solution::twoSum(nums, target);
    for (vector<int>::iterator it = id.begin(); it < id.end(); it++) {
        cout << *it<<" ";
    }
    system("pause");
    return 0;
}

• Two pointers(O(n) runtime, O(1) space)

C++:

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;

class Solution 
{
public:
    vector<int> static twoSum(vector<int>& nums, int target)
    {
        vector<int> id;
        int i = 0, j = nums.size() - 1;
        while (i<j) {
            if (nums[i] + nums[j] > target) j--;
            else if (nums[i] + nums[j] == target) return id = { i,j };
            else i++;
        }
        return id = { -1,-1 };
    }
};


int main(void)
{
    int n , target = 0;
    cin >> n;
    vector<int> nums(n);
    vector<int> id;
    for (int i = 0; i < nums.size(); i++) {
        cin >> nums[i];
    }
    cout << "Input your target:" << endl;
    cin >> target;
    id = Solution::twoSum(nums, target);
    for (vector<int>::iterator it = id.begin(); it < id.end(); it++) {
        cout << *it<<" ";
    }
    system("pause");
    return 0;
}

• Design a data structrue implement a TwoSum class

C++:

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;


class TwoSum {
private:
    static unordered_map<int, int> hash;
    static vector<int> id;
public:
    void static add(int num);
    bool static find(int target);
    void static print();
};

unordered_map<int, int> TwoSum::hash;
vector<int> TwoSum::id;

void TwoSum::add(int num) {
    (hash.find(num) == hash.end()) ? hash[num] = hash.size() : 0;

}

bool TwoSum::find(int target) {
    for (unordered_map<int, int>::iterator it = hash.begin(); it != hash.end(); it++) {
        if (hash.find(target - it->first) != hash.end()) {
            id = { it->second,hash[target - it->first] };
            return true;
        }            
    }
    return false;
}

void TwoSum::print() {
    cout << id[0] << " " << id[1] << endl;
}


int main(void)
{
    int n , target = 0,num;
    cin >> n;
    for (int i = 0; i <n; i++) {
        cin >> num;
        TwoSum::add(num);
    }
    cout << "Input your target:" << endl;
    cin >> target;
    if (TwoSum::find(target) == true) {
        TwoSum::print();
        }    
    system("pause");
    return 0;
}

原文地址：我的主页文章