LeetCode 1 Two Sum

发表于 | 更新于 | 分类于 | 阅读次数：

第一题总是比较简单的。

题目大意

题目给的是一个数组和一个目标数。

要求找到数组中和为目标数的两个数的下标。

同时告诉我们，解只有一个，同一个数不能使用两次。

举个例子：

输入：

1
2
nums = [2, 7, 11, 15];
target = 9;

那么结果应该是：

1
[0, 1]

解决方案

我们可以非常简单地得到一个暴力算法，用两层循环，外面一层找第一个数，第二层找第二个数，找到了就ok了。

每个循环中我们需要遍历整个数组，因此时间复杂度是$O(N^2)$。

既然是一个$O(N^2)$的算法，我们可以考虑通过排序来优化，毕竟排序只需要$O(\log{N})$的时间。

我们对数组排序之后，里面的一层循环就不需要遍历了，既然数组是有序的，我们可以用二分查找来找target和第一个数的差，如果是一个有效的并且和第一个数下标不同的位置，就说明我们找到了。

那么我们可以首先对数组进行排序，然后遍历数组中的元素，记这一次遍历下标为i，那么在遍历每个数的同时，我们在数组中二分查找target-nums[i]即可。

通过这种方式，我们可以将复杂度降低到$O(N\log{N})$。

还有更快的办法吗？想不出来了。

代码实现

随便写一写，反正也跑不了。实现一个二分查找就可以了。

1
2
3
4
5
6
7
8
9
function twoSum(nums, target) {
    const sorted = nums.sort();
    for(let i in sorted) {
        const j = binarySearch(sorted, target - sorted[i]);
        if(j >= 0 && i !== j) {
            return [i, j];
        }
    }
}