【LeetCode】第1题 两数之和

欢迎来到李耶的频道【LeetCode面试题】。两数之和题目给定一个整数数组nums和一个目标值target找出数组中和为目标值的两个数返回它们的下标。输入nums [2, 7, 11, 15], target 9 输出[0, 1]解法一对象缓存思路遍历数组用对象存已经看过的数。每到一个新数算一下target - 当前数是否在对象里在就说明配对成功直接返回两个下标。不在就把当前数存进对象继续往后遍历。functiontwoSum(nums,target){constseen{};for(leti0;inums.length;i){constcomplementtarget-nums[i];if(seen.hasOwnProperty(complement)){return[seen[complement],i];}seen[nums[i]]i;}return[];}时间复杂度O(n)只需遍历一次空间复杂度O(n)需要额外对象存储优势写法简单适合快速上手解法二Map思路和对象缓存完全一样只是换成 Map 数据结构。functiontwoSum(nums,target){constmapnewMap();for(leti0;inums.length;i){constcomplementtarget-nums[i];if(map.has(complement)){return[map.get(complement),i];}map.set(nums[i],i);}return[];}时间复杂度O(n)只需遍历一次空间复杂度O(n)需要额外 Map 存储优势Map 键可以是任意类型有 size 属性迭代更方便大数据量下性能更稳定扩展题三数之和找出所有和为 0 的三元组要求不重复。四数之和找出所有和为 target 的四元组。两数之和 II输入有序数组数组已升序排列找两数使和等于 target返回下标从1开始。两数之和 IV输入 BST给定二叉搜索树和一个目标值判断是否存在两个节点和等于 target。