一、题目来源：leetcode第一题
二、题目描述
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入： nums = [2,7,11,15], target = 9
输出： [0,1]
解释： 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入： nums = [3,2,4], target = 6
输出： [1,2]
示例 3：
输入： nums = [3,3], target = 6
输出： [0,1]
提示：
2 <= nums.length <= 10(4)-10(9) <= nums[i] <= 10(9)-10(9) <= target <= 10(9)- 只会存在一个有效答案
进阶： 你可以想出一个时间复杂度小于 O(n^2) 的算法吗？
三、解题
3.1 解法一
-
思路
两层for循环遍历，直到找到和为目标值 target 的那两个整数，并返回它们的数组下标。
-
解法
const twoSum = function ( nums, target ) {
for ( let i = 0 ; i < nums. length ; i++) {
for ( let j = i + 1 ; j < nums. length ; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
};
-
时间复杂度
该方法使用了两层嵌套的循环。外层循环从0到nums.length-1遍历数组中的每个元素，内层循环从外层循环的下一个元素开始遍历到数组的最后一个元素。因此，外层循环执行nums.length次，内层循环执行(nums.length-1) + (nums.length-2) + ... + 1次。在最坏情况下，内层循环的总执行次数约为(nums.length2)/2。因此，该方法的时间复杂度为**O(n2)** ，其中n是数组 nums 的长度。
-
空间复杂度
该方法只使用了常数级别的额外空间，即只创建了一个常数大小的数组来存储结果。因此，该方法的空间复杂度为O(1) 。
3.2 解法二
-
思路
我们可以先对 nums 排序，然后利用左右双指针，从两端相向而行找到和为目标值 target 的那两个整数，并返回在原始数组中它们的数组下标。
-
解法
const twoSum = function ( nums, target ) {
for ( let i = 0 ; i < nums. length ; i++) {
for ( let j = i + 1 ; j < nums. length ; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
};
-
时间复杂度
- 复制数组：
oringinalNums = [...nums]这一步需要遍历整个数组，因此时间复杂度为O(n)，其中n为数组nums的长度。 - 排序数组：
nums.sort((a, b) => a - b)这一步使用快速排序算法，其平均时间复杂度为O(nlogn)。 - 双指针移动：在while循环中，左指针和右指针进行移动，最多移动n次（即数组的长度），因此时间复杂度为O(n)。
- 综上所述，该方法的时间复杂度为O(nlogn) 。
-
空间复杂度
在算法中创建了一个新的数组oringinalNums来保存原始的nums，其长度与nums相同，因此需要O(n)的额外空间。其他变量的空间使用是常数级别的，不随输入规模变化，因此可以忽略。因此，总体空间复杂度为O(n) 。
3.3 解法三
-
思路
对于一个元素 nums[i]，你想知道有没有另一个元素 nums[j] 的值为 target - nums[i]，可以用一个哈希表记录每个元素的值到索引的映射，这样就能快速判断数组中是否有一个值为 target - nums[i] 的元素了。
-
解法
const twoSum = function ( nums, target ) {
// 维护 val -> index 的映射
const valToIndex = new Map ();
for ( let i = 0 ; i < nums. length ; i++) {
// 查表，看看是否有能和 nums[i] 凑出 target 的元素
const need = target - nums[i];
if (valToIndex. has (need)) {
return [valToIndex. get (need), i];
}
// 存入 val -> index 的映射
valToIndex. set (nums[i], i);
}
return null ;
};
-
时间复杂度
- 创建映射表：在for循环之前，通过
const valToIndex = new Map()创建了一个空的Map对象。这一步的时间复杂度是O(1)。 - 遍历数组并查找映射表：在for循环中，遍历了整个数组，并且对于每个元素，通过
valToIndex.has(need)进行查找，其中need是目标值与当前元素的差。Map查找的时间复杂度是O(1)。因此，整个遍历过程的时间复杂度是O(n)，其中n为数组nums的长度。 - 综上所述，该方法的时间复杂度为O(n) 。
-
空间复杂度
该方法使用了一个映射表valToIndex来存储元素值和索引的映射关系。在最坏的情况下，映射表需要存储整个数组的所有元素，因此空间复杂度为O(n) ，其中n为数组nums的长度。
四、知识点
常见时间复杂度，按照增长速率从小到大进行排序：
- O(1)：常数时间复杂度，表示算法的执行时间是一个常数，不随输入规模的增加而改变。例如，访问数组中的某个元素、进行固定次数的循环等。
- O(log n)：对数时间复杂度，表示算法的执行时间与输入规模的对数成正比。常见的具有对数时间复杂度的算法有二分查找、平衡二叉树的插入和删除操作等。
- O(sqrt(n))：平方根时间复杂度，表示算法的执行时间与输入规模的平方根成正比。例如，求解素数的方法中的试除法。
- O(n)：线性时间复杂度，表示算法的执行时间与输入规模成线性关系。例如，遍历数组、查找最大值或最小值等。
- O(n log n)：线性对数时间复杂度，表示算法的执行时间与输入规模的乘积与对数的乘积成正比。常见的具有线性对数时间复杂度的算法有快速排序、归并排序等。
- O(n^2)：平方时间复杂度，表示算法的执行时间与输入规模的平方成正比。例如，嵌套循环遍历二维数组、冒泡排序等。
- O(2^n)：指数时间复杂度，表示算法的执行时间随着输入规模的增加呈指数级增长。例如，求解斐波那契数列的递归算法。
- O(n!)：阶乘时间复杂度，表示算法的执行时间随着输入规模的增加呈阶乘级增长。例如，求解旅行商问题的穷举算法。
