找出数组中两数之和为指定值的所有整数对

左手的ㄟ右手 2021-12-18 06:45 266阅读 0赞

定一个整型数组（数组中的元素可重复，已排序），以及一个指定的值。找出数组中两数之和为指定值的所有整数对，要求时间复杂度为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)。接下来附上我的代码实现：

思路：

第一个思路，遍历数组中的某一个数，对于每个数再一次遍历数组中的所有数，找到满足条件的两个数。这个算法的时间复杂度为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

转载于:https://www.cnblogs.com/xiaosongJiang/p/10900646.html