网站建设元素如何叠加,做网站要提供什么,精品国内网站建设,门户网站开发分类目录 1.概念#xff1a;2.两数之和#xff08;1#xff09;.暴力破解法#xff08;2#xff09;.使用哈希表 3.区别 1.概念#xff1a; 非形式地说#xff0c;算法(algorithm)就是任何良定义的计算过程#xff0c;该过程取某个值或值的集合作为输入并产生某个值或值的集… 目录 1.概念2.两数之和1.暴力破解法2.使用哈希表 3.区别 1.概念 非形式地说算法(algorithm)就是任何良定义的计算过程该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。这样算法就是把输人转换成输出的计算步骤的一个序列。 我们也可以把算法看成是用于求解良说明的计算问题的工具。一般来说问题陈述说明了期望的输入/输出关系。算法则描述一个特定的计算过程来实现该输入/输出关系。 例如我们可能需要把一个数列排成非递减序。实际上这个问题经常出现并且为引人许多标准的设计技术和分析工具提供了足够的理由。下面是我们关于排序问题的形式定义。 输入;n个数的一个序列ala··a.。 输出:输人序列的一个排列a;a!·.·a,满足a1a2…an.例如给定输入序列《314159264158)排序算法将返回序列2631414158.59)作为输出。这样的输人序列称为排序问题的一个实例(instance)。一般来说问题实例由计算该问题解所必需的(满足问题陈述中强加的各种约束的)输入组成。 因为许多程序使用排序作为一个中间步所以排序是计算机科学中的一个基本操作。因此已有许多好的排序算法供我们任意使用。对于给定应用哪个算法最好依赖于以下因素:将被排序的项数、这些项已被稍微排序的程度、关于项值的可能限制、计算机的体系结构以及将使用的存储设备的种类(主存、磁盘或者磁带) 2.两数之和 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 例如
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。输入nums [3,2,4], target 6
输出[1,2]1.暴力破解法
针对这种问题我们可以使用双层for循环进行暴力破解示例代码如下
/*** param {number[]} nums* param {number} target* return {number[]}*/
var twoSum function(nums, target) {for (var i 0; i nums.length; i){for (var j i1 ; j nums.length ; j){if (nums[i] nums[j] target){return [i,j]}}}return {}
};针对这段代码我们进行大概的分析这段代码的时间复杂度为 O(n^2) 其中 n 是数组 nums 的长度。这是因为代码使用了两个嵌套的循环来遍历数组。第一个循环的时间复杂度为 O(n)第二个循环的时间复杂度取决于当前索引 i平均为 O(n/2)。因此总体的时间复杂度为 O(n * n/2)即 O(n^2)。
代码的空间复杂度为 O(1)因为它只使用了常量级的额外空间来存储变量 i、j并没有使用额外的数据结构或数组。无论输入的规模如何增长代码所需的额外空间量是固定的。 2.使用哈希表
/*** 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 complement target - nums[i];if (map.has(complement)) {return [map.get(complement), i]; // 找到两数之和等于目标值的索引}map.set(nums[i], i); // 将元素及其索引添加到哈希表}return []; // 若不存在两数之和等于目标值返回空数组
};这段代码使用了哈希表来降低时间复杂度使得时间复杂度为 O(n)其中 n 是数组 nums 的长度。具体解析如下
代码首先创建了一个空的哈希表 map用于存储数组元素及其索引。
在遍历数组 nums 的过程中对于每个元素 nums[i]通过计算 target - nums[i] 得到与之配对的补数 complement。
然后检查哈希表 map 中是否存在 complement如果存在说明在当前索引 i 之前已经出现过补数 complement即找到了满足条件的两个数可以直接返回两个索引的数组。
如果不存在 complement则将当前元素 nums[i] 及其索引 i 添加到哈希表 map 中。
最终如果没有找到满足条件的两个数返回一个空数组。
由于只需要遍历一次数组且哈希表的查找操作的时间复杂度为 O(1)因此总体时间复杂度为 O(n)。
空间复杂度方面额外使用了一个哈希表 map其所需空间取决于输入数组的大小因此空间复杂度为 O(n)。 3.区别
第一段代码使用了双重循环来遍历数组查找满足条件的两个数。虽然代码简单但时间复杂度为 O(n^2)在面对大规模数据时效率较低。此代码适用于数据量较小的情况。
第二段代码使用了哈希表来优化查找过程将时间复杂度降至 O(n)。这在处理大规模数据时表现更优。它以空间复杂度为代价利用哈希表存储元素及其索引以更快地查找到满足条件的两个数。
因此如果输入规模较小时第一段代码可能更简单且适用。而在处理大规模数据时第二段代码更有效率。
