定一个整型数组（数组中的元素可重复，已排序），以及一个指定的值。找出数组中两数之和为指定值的所有整数对，要求时间复杂度为O(N)。

     首先来分析一下这个题，假设题目没有说已排序和时间复杂度的要求，那么用最暴力的方法就是直接遍历两次数组，时间复杂度为O(N*N)。这里也来实现一下，代码如下：

 

/*暴力法，直接遍历两次数组，时间复杂度为O(n*n) */function getSum (arr, sum) {  if (arr == '' || arr.length == 0) {    return false;  }  for (var i = 0; i < arr.length; i++) {    for (var j = i + 1; j < arr.length; j++) {      if (arr[i] + arr[j] == sum) {        console.log(arr[i] + ' + ' + arr[j] + ' = ' + sum);      }    }  }}

 

      如果题目没有写明已排序，那么可以先将整型数组排序，排序之后定义两个指针left和right。left指向已排序数组中的第一个元素，right指向已排序数组中的最后一个元素，将 arr[left]+arr[right]与 给定的元素比较，若前者大，right--；若前者小，left++；若相等，则找到了一对整数之和为指定值的元素。此方法采用了排序，排序的时间复杂度为O(NlogN)，排序之后扫描整个数组求和比较的时间复杂度为O(N)。故总的时间复杂度为O(NlogN)，空间复杂度为O(1)。

     那么现在题目中已经写明已排序，所以就可以直接用上面的思路进行实现，那么时间复杂度就是O(N)。接下来附上我的代码实现：

function getSum (arr, sum) {  if (arr == '' || arr.length == 0) {    return false;  }  var left = 0; var right = arr.length - 1;  while (left < right) {    if (arr[left] + arr[right] > sum) {      right--;    } else if (arr[left] + arr[right] < sum) {      left++;    } else {      console.log(arr[left] + ' + ' + arr[right] + ' = ' + sum);      left++;      right--;    }  }}

 

  思路：

第一个思路，遍历数组中的某一个数，对于每个数再一次遍历数组中的所有数，找到满足条件的两个数。这个算法的时间复杂度为O(n2)，空间复杂度为O(1)。

第二个思路，在前一个算法的基础上降低时间复杂度。我们可以将数组排序，然后定义两个指针，一个指针从左向右，另一个从右向左，遍历直到找到满足条件的两个数。

由于排序的最佳时间复杂度为O(nlogn)，两个指针的遍历时间复杂度为O(n)。所以总的时间复杂度为O(nlogn)

第三个思路，我希望通过O(n)的时间复杂度完成要求。第一遍O(n)的算法将每个数据a对应的target-a建立查询的数据结构，例如Hash表；第二遍遍历时，查询每个数

是否在Hash表中，每次查询时间复杂度为O(1)，总的时间复杂度是O(n)。但是Hash表将需要一定的存储空间，为了节省空间，我们可以采用bitmap的方法来最大化的压

缩空间复杂度。

原文：https://blog.csdn.net/u010297791/article/details/70242559