Algorithm Problems: Two Sum

By | 2012 年 12 月 20 日

Manage two pointer to the array, one from the front, moving forward, the other from the rear, moving backward.
When the summation of the value pointed by the two pointer is equal to the given sum, then one solution is found;
Else if the summation is lower than the given sum, moving the lower pointer forward by 1 step;
Otherwise, moving the higher pointer backward by 1 step.
Doing this until the lower pointer meet the higher pointer.

Then the time complexity is O(n), space complexity is O(1).



Problem
Given an sorted integer array, ascending order, and a given number, find all the pairs in the array that sum to the given number.



Codes

//
//  main.cpp
//  TwoSum
//
//  Created by Qiu Xiangyu on 12-12-20.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > twoSum(vector<int> arr, int sum) {
    vector<vector<int> > ret;
    size_t low = 0, hi = arr.size() - 1;
    while (low < hi) {
        int vlow = arr[low];
        int vhi = arr[hi];
        int cursum = vlow + vhi;
        if (cursum == sum) {
            vector<int> sol(2,vlow);
            sol[1] = vhi;
            ret.push_back(sol);
            ++low;
        } else if (cursum < sum) {
            ++low;
        } else {
            --hi;
        }
    }
    return ret;
}

int main(int argc, const char * argv[])
{

    // insert code here...
    vector<int> arr = {1,2,3,4,5,6,7,8,9,10};
    vector<vector<int>> ret = twoSum(arr, 11);
    for (int i = 0; i < ret.size(); ++i) {
        vector<int> solution = ret[i];
        cout<<solution[0]<<" , "<<solution[1]<<endl;
    }
    cout<<"total : "<<ret.size()<<endl;
    return 0;
}

6 thoughts on “Algorithm Problems: Two Sum

    1. uniEagle Post author

      加入两次是正常的吧,题目上只说了所有的pair,但是没有指定是不是distinct的。如果是后者的话,只需要在每次找到pair的时候简单的处理一下就可以了。

      Reply
      1. chengbruce

        楼主最近在做leetcode题时搜答案看到你的博客了,然后觉得很多题都解释的思路清晰。 不知道你最近工作找怎么样?

        Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注