关于力扣第一题 ---两数之和（多方法）

2019-02-21 06:39:32来源：博客园阅读 ()

题目描述：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1.穷举法，两次遍历，暴力计算。使用第1个数与后面的每个数之和判断是否等于目标值、再用第2个数字做同样的操作，直到完全相等，返回索引值+1：
  两个循环，时间复杂度为O(N*N)

 1 var twoSum = function(nums, target) {
 2     for(var i = 0; i < nums.length - 1; i++){
 3         for(var j = i + 1; j < nums.length; j++) {
 4         if (nums[i] + nums[j] == target) {
 5             var arr = [];
 6             arr.push(i,j);
 7             return arr;
 8         }
 9       }
10    }
11 };

2.利用indexOf, Array 的 indexOf 方法实际上是对数组再遍历一次，写法上有优化，但是实际时间复杂度还是O(N*N):

 1 let twoSum = function(nums, target) {
 2     let a, b;
 3     for(let i = 0; i < nums.length; i++) {
 4         b = nums.indexOf(target - nums[i]);
 5         if(b > -1 && b !== i) {
 6             a = i;
 7             break;
 8         }
 9     }
10     return [a, b];
11 };

3.使用对象索引（时间复杂度低）：

创建一个对象，并给它赋值，对象的键值是我们想要检索的值，对象的值是在数组中的索引。

解题思路：构造了arr{ key：value} 对象。将target-nums[i] 差值放在arr{ }对象中，并存储其位置i。然后每次就在arr{ }对象中找有没有对应的数即可。

1 var twoSum = function(nums, target) {
2     var arr = {};
3     for (var i = 0; i < nums.length; i++) {
4         if (typeof(arr[nums[i]]) !== "undefined"){
5             return [arr[nums[i]], i];                        
6         }                         
7         arr[target - nums[i]] = i;
8     }
9 };

4.经典解题方法，排序+二分搜索

如果这个数据是有序的，那么我们很容易联想到使用二分搜索法,可以每次判断target-num[i]对应的值是否在num[i+1:]中，这个时候算法的复杂度变成了O(nlogn)。

 1 var twoSum = function getSum(arr,sum) {
 2     if(arr == '' || arr.length == 0){
 3         return false;
 4     }
 5     // arr.sort((a,b) => { return a-b });  如果是无序数组可先转为有序数组再使用二分搜索法
 6     var left = 0, right = arr.length -1;
 7     while(left < right){
 8         if(arr[left] + arr[right] > sum){
 9             right--;
10         }
11         else if(arr[left] + arr[right] < sum){
12             left++;
13         }
14         else{
15             return [left,right]; 
16             left++;
17             right--;
18         }
19     }
20 }

5.Hash方法，在所给数组中查找依次查找与当前值所对应的目标值是否存在，如果存在则记录当前index值。

 1 const twoSum = function(nums, target) {
 2    // 用于记录数组nums的长度
 3     const length = nums.length;
 4     // 实例化一个Map对象
 5     let hash = new Map();
 6     let index = 0;
 7     for (index = 0; index < length; index++) {
 8         // 设置 hashMap 的 <key, value>，用于后面比较取值
 9         hash.set(nums[index], index);
10     }
11  
12  
13     // 遍历数组中的每一个数，求出另一个与其相加可以满足条件的数的值，存储在 @param numToFind 中
14     let numToFind;
15     for( index = 0; index < length; index++) {
16          numToFind = target - nums[index];
17          // 查询 hashMap 中对应的值是否有对应的index，而且不能是当前数的下标（防止出现 3 + 3 = 6，但数组nums中只有一个3这样的情况）
18          if (hash.has(numToFind) && index !== hash.get(numToFind)) {
19               return [index, hash.get(numToFind)];
20          }
21      }
22 };