LEETCODE 1. 两数之和
题解地址
https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
有人相爱,有人夜里开车看海,有人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 <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?
分析
方法一:暴力枚举
思路及算法
最容易想到的方法是枚举数组中的每一个数 x,寻找数组中是否存在 target – x。
当我们使用遍历整个数组的方式寻找 target – x 时,需要注意到每一个位于 x 之前的元素都已经和 x 匹配过,因此不需要再进行匹配。而每一个元素不能被使用两次,所以我们只需要在 x 后面的元素中寻找 target – x。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
上述代码是一个简单的解决LeetCode上”两数之和”问题的实现。下面对该代码的复杂度进行分析。
设输入的数组长度为n。
- 外层循环:i从0到n-1,共进行n次迭代。
- 内层循环:j从i+1到n-1,平均情况下进行(n-1-i)/2次迭代(假设n足够大)。
因此,总的迭代次数为:
n + (n-1) + (n-2) + … + 1 ≈ n^2 / 2
由于内层循环中只有常数次的操作,可以忽略不计,所以算法的时间复杂度为O(n^2)。
在空间复杂度方面,除了存储结果的返回数组外,算法并没有使用额外的空间,因此空间复杂度为O(1)(常数级别)。
需要注意的是,由于解决两数之和问题的最优解是哈希表,其时间复杂度为O(n),因此上述代码存在较高的时间复杂度,不是最优解。但在一些规模较小的问题上,该算法的实际性能可能仍然可接受。
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
方法二:哈希表
哈希表(Hash Table),也被称为散列表,是一种常用的数据结构。它通过利用哈希函数(Hash Function)来实现快速的数据插入、删除和查找操作。
哈希表由一个数组和哈希函数组成。哈希函数将每个元素映射到数组中的一个位置,该位置称为哈希值或哈希码。数组的索引即为哈希值,可以直接访问到对应位置的元素。
具体的工作原理如下:
- 对于要插入或查找的元素,首先经过哈希函数得到它的哈希值。
- 将元素存储在计算得到的哈希值对应的数组位置上。
- 若存在相同的哈希值,则可能发生冲突(Hash Collision)。冲突可以通过使用开放寻址法和链地址法来解决。
- 开放寻址法:当发生冲突时,不断地探测下一个空闲位置,直到找到合适的位置插入元素。
- 链地址法:在哈希表的每个位置上维护一个链表,每个链表存储哈希值相同的元素,冲突时将元素插入链表中。
- 插入和查找元素时,再次通过哈希函数计算哈希值,然后在对应位置上进行操作。
哈希表通过利用哈希函数的快速计算和数组的随机访问特性,实现了高效的元素插入、删除和查找。在理想情况下,哈希表的插入、删除和查找操作的平均时间复杂度为O(1)。
哈希表在很多应用中都得到广泛的使用,例如数据库索引、缓存系统、编译器中的符号表等。
思路及算法
注意到方法一的时间复杂度较高的原因是寻找 target – x 的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
上述代码是使用哈希表来解决LeetCode上”两数之和”问题的实现。该算法的时间复杂度为O(n),空间复杂度为O(n)。
具体分析如下:
- 创建一个哈希表 hashtable,用于存储数组中的元素及其对应的索引。
- 遍历数组 nums,对于每个元素 nums[i],进行以下操作:
- 在哈希表 hashtable 中寻找是否存在 target – nums[i] 的键值对,即找到了另外一个数与当前数之和为目标值 target。
- 如果找到了,返回对应的索引和当前元素的索引。
- 如果没有找到,将当前元素 nums[i] 插入哈希表 hashtable 中,键为元素值,值为元素索引。
- 如果遍历结束仍未找到满足条件的元素对,返回空数组。
在这个算法中,通过哈希表的快速查找特性,将寻找 target – x 的时间复杂度降低为O(1)。因此,总的时间复杂度为O(n)。同时,哈希表用来存储元素及其索引,所需的额外空间为O(n)。
相比于方法一,方法二使用哈希表使得算法的时间复杂度大幅降低,是更优的解法。
进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?
当然可以!通过使用两个指针,可以将时间复杂度降低到O(n)。下面是一个优化的算法:
假设有一个排序好的数组,并且我们要找到两个数之和等于目标值target。使用双指针方法可以高效地解决这个问题。
- 初始化两个指针left和right,分别指向数组的开头和结尾。
- 计算两个指针指向的元素的和sum。
- 如果sum等于target,那么找到了两个数的和等于目标值,返回它们的索引。
- 如果sum小于target,说明需要增加两个数的和,因此将left指针右移一位。
- 如果sum大于target,说明需要减小两个数的和,因此将right指针左移一位。
- 重复步骤2直到找到满足条件的两个数,或者left大于等于right时停止搜索。
这个算法的时间复杂度为O(n),因为在最坏情况下,我们需要遍历数组一次。而空间复杂度仍为O(1),因为只需要额外存储两个指针的索引。
需要注意的是,这个方法适用于已经排序好的数组。如果输入的数组无序,我们可以先对其进行排序,然后再使用双指针方法。
def two_sum(nums, target):
left = 0
right = len(nums) - 1
while left < right:
sum = nums[left] + nums[right]
if sum == target:
return [left, right]
elif sum < target:
left += 1
else:
right -= 1
# 若找不到满足条件的两个数,则返回空列表
return []
# 示例输入
nums = [-2, 0, 3, 6, 7, 9, 11]
target = 9
result = two_sum(nums, target)
if result:
print("找到满足条件的两个数的索引:", result)
else:
print("找不到满足条件的两个数")
代码随想录:
https://www.bilibili.com/video/BV1aT41177mK/
思路
很明显暴力的解法是两层for循环查找,时间复杂度是O(n^2)。
本题呢,则要使用map,那么来看一下使用数组和set来做哈希法的局限。
数组的大小是受限制的,而且如果元素很少,而哈希值太大会造成内存空间的浪费。
set是一个集合,里面放的元素只能是一个key,而两数之和这道题目,不仅要判断y是否存在而且还要记录y的下表位置,因为要返回x 和 y的下表。所以set 也不能用。
此时就要选择另一种数据结构:map ,map是一种key value的存储结构,可以用key保存数值,用value在保存数值所在的下表。
C++中map,有三种类型: !如图
std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。
同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。 更多哈希表的理论知识请看关于哈希表,你该了解这些!。
这道题目中并不需要key有序,选择std::unordered_map 效率更高!使用其他语言的录友注意了解一下自己所用语言的map结构的内容实现原理。
接下来需要明确两点:
map用来做什么
map中key和value分别表示什么
map目的用来存放我们访问过的元素,因为遍历数组的时候,需要记录我们之前遍历过哪些元素和对应的下表,这样才能找到与当前元素相匹配的(也就是相加等于target)
接下来是map中key和value分别表示什么。
这道题 我们需要 给出一个元素,判断这个元素是否出现过,如果出现过,返回这个元素的下标。
那么判断元素是否出现,这个元素就要作为key,所以数组中的元素作为key,有key对应的就是value,value用来存下标。
所以 map中的存储结构为 {key:数据元素,value:数组元素对应的下表}。
在遍历数组的时候,只需要向map去查询是否有和目前遍历元素比配的数值,如果有,就找到的匹配对,如果没有,就把目前遍历的元素放进map中,因为map存放的就是我们访问过的元素。
过程如下:
!过程一
!过程二
C++代码:
class Solution {
public:
vector twoSum(vector& nums, int target) {
std::unordered_map <int,int> map;
for(int i = 0; i < nums.size(); i++) {
// 遍历当前元素,并在map中寻找是否有匹配的key
auto iter = map.find(target – nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
// 如果没找到匹配对,就把访问过的元素和下标加入到map中
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
总结
这道题目关键是在于明确map是用来做什么的,map中的key和value用来存什么的。
这个想清楚了,题目代码就比较清晰了。
很多录友把这道题目 通过了,但都没想清楚map是用来做什么的,以至于对代码的理解其实是 一知半解的。
其他语言版本
Java:
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
if(nums == null || nums.length == 0){
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i];
if(map.containsKey(temp)){
res[1] = i;
res[0] = map.get(temp);
}
map.put(nums[i], i);
}
return res;
}
Python:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
records = dict()
# 用枚举更方便,就不需要通过索引再去取当前位置的值
for idx, val in enumerate(nums):
if target - val not in records:
records[val] = idx
else:
return [records[target - val], idx] # 如果存在就返回字典记录索引和当前索引
Go:
func twoSum(nums []int, target int) []int {
for k1, _ := range nums {
for k2 := k1 + 1; k2 < len(nums); k2++ {
if target == nums[k1] + nums[k2] {
return []int{k1, k2}
}
}
}
return []int{}
}
// 使用map方式解题,降低时间复杂度
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for index, val := range nums {
if preIndex, ok := m[target-val]; ok {
return []int{preIndex, index}
} else {
m[val] = index
}
}
return []int{}
}
Rust
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::with_capacity(nums.len());
for i in 0..nums.len() {
if let Some(k) = map.get(&(target - nums[i])) {
if *k != i {
return vec![*k as i32, i as i32];
}
}
map.insert(nums[i], i);
}
panic!("not found")
}
}
Javascript
var twoSum = function (nums, target) {
let hash = {};
for (let i = 0; i < nums.length; i++) {
if (hash[target - nums[i]] !== undefined) {
return [i, hash[target - nums[i]]];
}
hash[nums[i]] = i;
}
return [];
};
php
function twoSum(array $nums, int $target): array
{
for ($i = 0; $i < count($nums);$i++) {
// 计算剩下的数
$residue = $target - $nums[$i];
// 匹配的index,有则返回index, 无则返回false
$match_index = array_search($residue, $nums);
if ($match_index !== false && $match_index != $i) {
return array($i, $match_index);
}
}
return [];
}
Swift:
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var res = [Int]()
var dict = [Int : Int]()
for i in 0 ..< nums.count {
let other = target - nums[i]
if dict.keys.contains(other) {
res.append(i)
res.append(dict[other]!)
return res
}
dict[nums[i]] = i
}
return res
}
Scala:
object Solution {
// 导入包
import scala.collection.mutable
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
// key存储值,value存储下标
val map = new mutable.HashMap[Int, Int]()
for (i <- nums.indices) {
val tmp = target - nums(i) // 计算差值
// 如果这个差值存在于map,则说明找到了结果
if (map.contains(tmp)) {
return Array(map.get(tmp).get, i)
}
// 如果不包含把当前值与其下标放到map
map.put(nums(i), i)
}
// 如果没有找到直接返回一个空的数组,return关键字可以省略
new Array[Int](2)
}
}
C#:
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int ,int> dic= new Dictionary<int,int>();
for(int i=0;i<nums.Length;i++){
int imp= target-nums[i];
if(dic.ContainsKey(imp)&&dic[imp]!=i){
return new int[]{i, dic[imp]};
}
if(!dic.ContainsKey(nums[i])){
dic.Add(nums[i],i);
}
}
return new int[]{0, 0};
}
}
画图解
版权声明:本文为博主作者:时雨h原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/shaozheng0503/article/details/131492073