1. AI技术聚合首页
  2. IT

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

社会演员多 • • IT • 阅读 44

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)
社会演员多的头像社会演员多普通用户
0
上一篇 2023年12月29日
下一篇 2023年12月29日

相关推荐