Interview----2 sum

题目:输入一个已经按升序排序过的数组和一个数字,

在数组中查找两个数,使得它们的和正好是输入的那个数字。

要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。

例如输入数组 1、2、4、7、11、15 和数字 15。由于 4+11=15,因此输出 4 和 11。

分析：

给出两种算法： 1. 枚举第一个，然后二分搜索第二个数。 O（NlgN)

2. 双指针法。 left, right 分别指向首尾，如果 a[left] + a[right] < sum, left++, 如果 >, right --; 否则找到答案

扩充：找出 3个数，使其和等于 sum. 见点击打开链接

// copyright @ L.J.SHOU Mar.05, 2014

// 2 sum

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// O(NlgN)

void TwoSumVersion1(vector<int> &a, int sum)

{

  if(a.size() < 2)

    return;

  for(vector<int>::iterator it = a.begin(); it != a.end(); ++it)

  {

    if(binary_search(a.begin(), it, sum - *it)

	    || binary_search(it+1, a.end(), sum - *it))

	{

	  cout << *it << " " << sum - *it << endl;

	  return;

	}

  }

}

// two pointers O(N)

void TwoSumVersion2(vector<int> &a, int sum)

{

  vector<int>::iterator left(a.begin()), right(a.end()-1); 

  while(left < right)

  {

    if(*left + *right < sum){

	  ++ left;

	}

	else if(*left + *right > sum){

	  -- right;

	}

	else{

	  cout << *left << " " << *right << endl;

	  return;

	}

  }

}

int main(void)

{

  int a[]={1,2,4,7,11,15};

  vector<int> vec(a, a+sizeof(a)/sizeof(int));

  TwoSumVersion1(vec, 15);

  TwoSumVersion2(vec, 15);

  return 0;

}

巴特西

Interview----2 sum

最新文章

热门文章