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

这篇具有很好参考价值的文章主要介绍了有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来​​。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LEETCODE 1. 两数之和

有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来​​,C++,比赛,C++刷题,leetcode,算法,职场和发展

题解地址
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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法二:哈希表

有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来​​,C++,比赛,C++刷题,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};
    }
}

画图解

有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来​​,C++,比赛,C++刷题,leetcode,算法,职场和发展
有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来​​,C++,比赛,C++刷题,leetcode,算法,职场和发展
有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来​​,C++,比赛,C++刷题,leetcode,算法,职场和发展
有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来​​,C++,比赛,C++刷题,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/news/detail-542320.html

到了这里,关于有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来​​的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • web爬虫第五弹 - JS逆向入门(猿人学第一题)

    0- 前言 爬虫是一门需要实战的学问。 而对于初学者来说,要想学好反爬,js逆向则是敲门砖。今天给大家带来一个js逆向入门实例,接下来我们一步一步来感受下入门的逆向是什么样的。该案例选自猿人学练习题。猿人学第一题 1- 拿到需求 进入页面拿到需求我们先不要急着

    2024年02月14日
    浏览(35)
  • 贴完车衣开车就走?

    贴完车衣之后,你以为直接开走就好了吗? 大错特错!!! 正确流程,记得收藏起来! 1:膜开箱:这个当场开箱,防止偷梁换柱 2:装贴过程:确认施工回执单,标注清楚品牌、质保时间、价格及其他要求,纸质文件。 3:验车:检验全车贴膜有没有划伤,漆面、大灯、轮

    2023年04月17日
    浏览(34)
  • leetcode每日一题44

    图论 dfs/bfs dfs代码框架 思路:本题要求找到被x围绕的陆地,所以边界的陆地O肯定不符合条件。那么我们只要从周边找到陆地O然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地O都变成A,然后再去重新遍历地图的时候,把剩下的O变成X,再把所有的A变成O。 确认递归函数,参数

    2024年01月19日
    浏览(43)
  • 物联网与 Linux 的相爱相生

    Linux 无疑将在物联网中扮演一个关键角色,但是其光彩将与其它的一些分享。 随着 Canonical 重新关注于赢利和新技术,我们中的一些人发现我们正在思考 Linux 未来将走向何方,IoT(物联网)是否是 Linux 的未来? 本文旨在解决这两个问题。 Mycroft 运行于 Linux 对于大多数非技

    2024年02月08日
    浏览(31)
  • 米哈游春招后端-2023.03.19-第一题-米哈游的RBG矩阵-简单

    米哈游的RBG矩阵 Problem Description 米小游拿到了一个矩阵,矩阵上有一格有一个颜色,为红色( R )。绿色( G )和蓝色( B )这三种颜色的一种。 然而米小游是蓝绿色盲,她无法分游蓝色和绿色,所以在米小游眼里看来,这个矩阵只有两种颜色,因为蓝色和绿色在她眼里是一种颜色。

    2023年04月09日
    浏览(33)
  • 这款知名开车软件,居然暗藏大量病毒

    想必大家见多了网上有关 Windows 系统宝藏神级软件的种种推荐。 其中有这么一款软件一直占据推荐榜单前列,并且坐拥无数好评。 它就是在 Steam 上售价仅 19 元,表面看起来平平无奇的 Wallpaper Engine (壁纸引擎)。 别看它价格不到一碗小份黄焖鸡,能带给你的快乐却是丝毫

    2023年04月22日
    浏览(43)
  • 【LeetCode每日一题】——85.最大矩形

    矩阵 困难 85.最大矩形 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例 1: 输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“

    2024年02月13日
    浏览(38)
  • 【每日一题】Leetcode - 283. 移动零

    Leetcode - 283. 移动零 从右向左遍历,遇到0,就将后面所有元素前移,同时更新长度,使其减1,因为移动n次,倒数n位就被0占据,后续操作可忽略 前面的操作,从右向左,每次遇到0移动都要跑半个数组,慢在整体前移; 换个思路,从左向右,记录首个0的位置,将后面的第一

    2024年02月11日
    浏览(43)
  • 【LeetCode每日一题】——566.重塑矩阵

    矩阵 简单 566.重塑矩阵 在 MATLAB 中,有一个非常有用的函数 reshape ,它可以将一个 m x n 矩阵重塑为另一个大小不同(r x c)的新矩阵,但保留其原始数据。 给你一个由二维数组 mat 表示的 m x n 矩阵,以及两个正整数 r 和 c ,分别表示想要的重构的矩阵的行数和列数。 重构后

    2024年02月14日
    浏览(46)
  • 每日一题(LeetCode)----二分查找(一)

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 104 -104 = nums[i] = 104 nums 为 无重复元素 的 升序 排列数

    2024年02月08日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包