有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来

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。

  1. 外层循环:i从0到n-1,共进行n次迭代。
  2. 内层循环: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)来实现快速的数据插入、删除和查找操作。

哈希表由一个数组和哈希函数组成。哈希函数将每个元素映射到数组中的一个位置,该位置称为哈希值或哈希码。数组的索引即为哈希值,可以直接访问到对应位置的元素。

具体的工作原理如下:

  1. 对于要插入或查找的元素,首先经过哈希函数得到它的哈希值。
  2. 将元素存储在计算得到的哈希值对应的数组位置上。
  3. 若存在相同的哈希值,则可能发生冲突(Hash Collision)。冲突可以通过使用开放寻址法和链地址法来解决。
    • 开放寻址法:当发生冲突时,不断地探测下一个空闲位置,直到找到合适的位置插入元素。
    • 链地址法:在哈希表的每个位置上维护一个链表,每个链表存储哈希值相同的元素,冲突时将元素插入链表中。
  4. 插入和查找元素时,再次通过哈希函数计算哈希值,然后在对应位置上进行操作。

哈希表通过利用哈希函数的快速计算和数组的随机访问特性,实现了高效的元素插入、删除和查找。在理想情况下,哈希表的插入、删除和查找操作的平均时间复杂度为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)。

具体分析如下:

  1. 创建一个哈希表 hashtable,用于存储数组中的元素及其对应的索引。
  2. 遍历数组 nums,对于每个元素 nums[i],进行以下操作:
    • 在哈希表 hashtable 中寻找是否存在 target – nums[i] 的键值对,即找到了另外一个数与当前数之和为目标值 target。
    • 如果找到了,返回对应的索引和当前元素的索引。
    • 如果没有找到,将当前元素 nums[i] 插入哈希表 hashtable 中,键为元素值,值为元素索引。
  3. 如果遍历结束仍未找到满足条件的元素对,返回空数组。

在这个算法中,通过哈希表的快速查找特性,将寻找 target – x 的时间复杂度降低为O(1)。因此,总的时间复杂度为O(n)。同时,哈希表用来存储元素及其索引,所需的额外空间为O(n)。

相比于方法一,方法二使用哈希表使得算法的时间复杂度大幅降低,是更优的解法。

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

当然可以!通过使用两个指针,可以将时间复杂度降低到O(n)。下面是一个优化的算法:

假设有一个排序好的数组,并且我们要找到两个数之和等于目标值target。使用双指针方法可以高效地解决这个问题。

  1. 初始化两个指针left和right,分别指向数组的开头和结尾。
  2. 计算两个指针指向的元素的和sum。
    • 如果sum等于target,那么找到了两个数的和等于目标值,返回它们的索引。
    • 如果sum小于target,说明需要增加两个数的和,因此将left指针右移一位。
    • 如果sum大于target,说明需要减小两个数的和,因此将right指针左移一位。
  3. 重复步骤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

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
社会演员多的头像社会演员多普通用户
上一篇 2023年12月29日
下一篇 2023年12月29日

相关推荐

此站出售,如需请站内私信或者邮箱!