【LeetCode】第1题 两数之和

欢迎来到李耶的频道【LeetCode面试题】。

两数之和

题目

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

输入：nums = [2, 7, 11, 15], target = 9 输出：[0, 1]

解法一：对象缓存

思路：遍历数组，用对象存已经看过的数。每到一个新数，算一下target - 当前数是否在对象里，在就说明配对成功，直接返回两个下标。不在就把当前数存进对象，继续往后遍历。

functiontwoSum(nums,target){constseen={};for(leti=0;i<nums.length;i++){constcomplement=target-nums[i];if(seen.hasOwnProperty(complement)){return[seen[complement],i];}seen[nums[i]]=i;}return[];}

• 时间复杂度：O(n)，只需遍历一次
• 空间复杂度：O(n)，需要额外对象存储
• 优势：写法简单，适合快速上手

解法二：Map

思路：和对象缓存完全一样，只是换成 Map 数据结构。

functiontwoSum(nums,target){constmap=newMap();for(leti=0;i<nums.length;i++){constcomplement=target-nums[i];if(map.has(complement)){return[map.get(complement),i];}map.set(nums[i],i);}return[];}

• 时间复杂度：O(n)，只需遍历一次
• 空间复杂度：O(n)，需要额外 Map 存储
• 优势：Map 键可以是任意类型，有 size 属性，迭代更方便，大数据量下性能更稳定

扩展题

1. 三数之和：找出所有和为 0 的三元组，要求不重复。
2. 四数之和：找出所有和为 target 的四元组。
3. 两数之和 II：输入有序数组，数组已升序排列，找两数使和等于 target，返回下标（从1开始）。
4. 两数之和 IV：输入 BST，给定二叉搜索树和一个目标值，判断是否存在两个节点和等于 target。