题目

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

暴力解法

通过两次循环依次比对i和i+1的值计算结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for(int i = 0; i < numsSize; i++) {
        for(int j = i + 1; j <numsSize; j++) {
            if(nums[i] + nums[j] == target) {
                *returnSize = 2;
                int* rtn = (int*)malloc(sizeof(int) * 2);
                rtn[0] = i;
                rtn[1] = j;
                return rtn;
            }
        }
    }
    return NULL;
}

第一次循环

1
2

2 7 11 15
i j

第一次第二层循环

1
2

2 7 11 15
i    j

……
第二次第一层循环：

1
2
3

2 7 11 15
(i++)
j  i  

1
2

2 7 11 15
  i j

1
2

2 7 11 15
  i     j

这种算法简单好写，缺点是时间复杂度高，处理大型数据时性能捉急。

哈希表法

分析

假设函数输入还是同上，2, 7, 11, 15

建立一个哈希表，由于我们需要的是元素的索引，就把索引存到value里，用元素作为key来查找。

1
2
3
4
5
6
7
8

target = 9
-----------
key  value
2    0
7    1
11   2
15   3
-----------

尝试用target - key，得到的差就是要在表中查找的值。

比如用target: 9 - key[0] = 7；

这时候在表中找一下有没有这个数，然后返回它的value和减数的value即可。

实现

用JavaScript的map函数来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
   const map = new Map()
   for(let i = 0; i < nums.length; i++) {
    const a = target - nums[i]
    if(map.has(a)) {
        return [map.get(a), i];
    }
    map.set(nums[i], i)
   }
   return [];
};

创建map对象，循环查找key:a，返回下标。时间复杂度O(n)。