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 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
unordered_map
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
总结
这道题目关键是在于明确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
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
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
for(int i=0;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}; } } 画图解 参考阅读
您阅读本篇文章共花了：
发表评论
2024-06-15 11:13:38回复
1. 代码实现没有进行错误处理，例如输入的数组为空、目标值超出范围等情况。
2. 没有对输入参数进行有效性检查，可能导致程序在运行过程中出现异常。
3. 代码可读性较差，没有进行合适的注释和格式化。
4. 代码实现没有充分利用已有的哈希表等数据结构，导致时间复杂度过高。
问题：如何提高代码的效率和可读性？