【经典算法】LeetCode1:两数之和(Java/C/Python3实现含注释说明,Easy)

2024-03-31 14:20

本文主要是介绍【经典算法】LeetCode1:两数之和(Java/C/Python3实现含注释说明,Easy),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

两数之和

  • 题目
  • 思路及实现
    • 方式一:暴力解法(不推荐)
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
      • 复杂度分析
    • 方式二:哈希表(推荐)
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
      • 复杂度分析
    • 方式三:双指针法
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
      • 复杂度分析
  • 总结
  • 相似题目

  • 标签:哈希表、查找

题目

给定一个整数数组 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
只会存在一个有效答案

原题:LeetCode 1

思路及实现

方式一:暴力解法(不推荐)

思路

最容易想到的方法是枚举数组中的每一个数 x,寻找数组中是否存在 target - x。
当我们使用遍历整个数组的方式寻找 target - x 时,需要注意到每一个位于 x 之前的元素都已经和 x 匹配过,因此不需要再进行匹配。而每一个元素不能被使用两次,所以我们只需要在 x 后面的元素中寻找 target - x。

代码实现

Java版本

public int[] twoSum(int[] nums, int target) {int n = nums.length;for (int i = 0; i < nums.length; i++) { // 遍历数组,从第一个元素开始for (int j = i + 1; j < nums.length; j++) { // 在当前元素后面的元素中查找与目标值相加等于target的元素if (nums[i] + nums[j] == target) { // 如果找到了符合条件的元素对return new int[]{i, j}; // 返回这两个元素的下标}}}return new int[0]; // 如果没有找到符合条件的元素对,则返回空数组
}
C语言版本
#include <stdio.h>
#include <stdlib.h>int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int* result = (int*)malloc(2 * sizeof(int)); // 分配保存结果的内存空间*returnSize = 0; // 初始化返回结果数组的大小为0,表示没有找到满足条件的元素对for (int i = 0; i < numsSize; i++) { // 外层循环遍历数组中的每个元素for (int j = i + 1; j < numsSize; j++) { // 内层循环遍历当前元素后面的每个元素if (nums[i] + nums[j] == target) { // 检查两个元素的和是否等于目标值result[0] = i; // 将符合条件的第一个元素的下标存入结果数组的第一个位置result[1] = j; // 将符合条件的第二个元素的下标存入结果数组的第二个位置*returnSize = 2; // 更新返回结果数组的大小为2return result; // 返回结果数组}}}return result; // 返回结果数组,如果没有找到满足条件的元素对,数组中的元素值均为0// 注意:需要在适当的时候释放result指向的动态分配内存,以避免内存泄漏
}
Python3版本
from typing import List
def twoSum(nums: List[int], target: int) -> List[int]:result = [] # 用于存储结果的列表n = len(nums)for i in range(n): # 外层循环遍历列表中的每个元素for j in range(i+1, n): # 内层循环遍历当前元素后面的每个元素if nums[i] + nums[j] == target: # 检查两个元素的和是否等于目标值result.append(i) # 将符合条件的第一个元素的下标添加到结果列表中result.append(j) # 将符合条件的第二个元素的下标添加到结果列表中return result # 返回结果列表return result # 如果没有找到满足条件的元素对,返回空列表

复杂度分析

  • 时间复杂度分析:O(n^2),其中n为数组nums的长度。这是由于代码使用了两层循环来遍历数组。外层循环将执行n次,而内层循环则将执行(n-1)次、(n-2)次、…、2次、1次,总的执行次数为n * (n-1) / 2,即O(n^2)。

  • 空间复杂度分析:O(1),即常数级别的空间复杂度。因为代码只使用了常数个额外变量来存储元素的下标和存储结果的数组。

方式二:哈希表(推荐)

思路

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。

使用哈希表,可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表,对于每一个 x,我们首先查询哈希表中是否存在 target - x,然后将 x 插入到哈希表中,即可保证不会让 x 和自己匹配。

代码实现

Java版本
import java.util.HashMap;class Solution {public int[] twoSum(int[] nums, int target) {//key为当前值,value为当前值的位置HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i]; // 计算差值,即目标值与当前元素的差值if (map.containsKey(complement)) {return new int[]{map.get(complement), i}; // 返回HashMap中保存的差值元素的下标和当前元素的下标}map.put(nums[i], i); // 将当前元素添加到HashMap中}return new int[0]; // 如果没有找到满足条件的元素对,返回空数组}
}

说明:

C语言版本
#include <stdio.h>
#include <stdlib.h>int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int* result = (int*)malloc(2 * sizeof(int));*returnSize = 0;// 创建哈希表int hashtable[20001] = {0};for (int i = 0; i < numsSize; ++i) {int complement = target - nums[i]; // 计算差值,即目标值与当前元素的差值// 检查哈希表中是否存在差值if (complement >= -10000 && complement <= 10000 && hashtable[complement + 10000] != 0) {result[0] = hashtable[complement + 10000] - 1; // 返回哈希表中保存的差值元素的下标result[1] = i; // 返回当前元素的下标*returnSize = 2; // 更新返回结果数组的大小为2return result;}// 将当前元素添加到哈希表中hashtable[nums[i] + 10000] = i + 1;}return result;
}
Python3版本
from typing import List
from collections import defaultdictclass Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:hashtable = defaultdict(int) # 使用defaultdict来容纳哈希表for i in range(len(nums)):complement = target - nums[i] # 计算差值,即目标值与当前元素的差值if complement in hashtable:return [hashtable[complement], i] # 返回哈希表中保存的差值元素的下标和当前元素的下标hashtable[nums[i]] = i # 将当前元素添加到哈希表中return [] # 如果没有找到满足条件的元素对,返回空列表

复杂度分析

  • 时间复杂度:O(N),其中 N 是数组中的元素数量。对于每一个元素 x,我们可以 O(1) 地寻找 target - x。
  • 空间复杂度:O(N),其中 N 是数组中的元素数量。主要为哈希表的开销。

方式三:双指针法

思路

双指针法是解决两数之和问题的一种常见方法。其思路是首先对输入数组进行排序,然后使用两个指针指向数组的起始位置和结束位置。在每一步迭代中,计算两个指针对应元素的和,并与目标值进行比较。

如果和等于目标值,说明找到了满足条件的两个数,返回它们的索引。
如果和小于目标值,说明需要增加和,因此将左指针向右移动一位。
如果和大于目标值,说明需要减少和,因此将右指针向左移动一位。
重复上述步骤直到找到满足条件的两个数或者左右指针相遇。

双指针法的优点是时间复杂度相对较低,只需要对数组进行一次排序,并且在有序数组中移动指针来寻找目标值,从而减少了比较次数。同时,该方法只需要常数级的额外空间。然而,需要注意的是双指针法要求输入数组必须是有序的,这会导致对原始数组的修改。

实现时可以使用Java的Arrays工具类对数组进行排序,然后使用左右指针按照上述思路进行迭代,最终找到满足条件的两个数或者返回空数组表示未找到。

代码实现

Java版本
import java.util.Arrays;public class TwoSum {public int[] twoSum(int[] nums, int target) {// 对数组进行排序Arrays.sort(nums);// 初始化左右指针int left = 0;int right = nums.length - 1;while (left < right) {// 计算当前左右指针对应元素之和int sum = nums[left] + nums[right];if (sum == target) {// 找到目标值,返回对应的数组下标return new int[]{left, right};} else if (sum < target) {// sum小于目标值,将左指针向右移动一位left++;} else {// sum大于目标值,将右指针向左移动一位right--;}}// 没有找到满足条件的两个数,返回空数组return new int[]{};}
}

说明:
twoSum 方法接收一个整数数组 nums 和目标值 target,返回一个包含两个数的索引的整数数组,其中这两个数的和等于目标值。
首先使用 Arrays.sort(nums) 对数组进行排序。
初始化左指针 left 指向数组的起始位置,右指针 right 指向数组的结束位置。
使用 while 循环迭代,当左指针小于右指针时:
计算当前左右指针对应元素之和 sum。
如果 sum 等于目标值 target,则返回一个包含左右指针的整数数组。
如果 sum 小于目标值 target,将左指针向右移动一位。
如果 sum 大于目标值 target,将右指针向左移动一位。
如果循环结束后仍然没有找到满足条件的两个数,返回一个空数组。
需要注意的是,在返回结果后,需要及时释放动态分配的内存。

C语言版本
#include <stdio.h>
#include <stdlib.h>int* twoSum(int* nums, int numsSize, int target) {// 对数组进行排序(可以使用快速排序等)qsort(nums, numsSize, sizeof(int), compare);// 初始化左右指针int left = 0;int right = numsSize - 1;while (left < right) {// 当前左右指针对应元素之和int sum = nums[left] + nums[right];if (sum == target) {// 找到目标值,返回对应的数组下标int* result = (int*)malloc(2 * sizeof(int));result[0] = left;result[1] = right;return result;} else if (sum < target) {// sum小于目标值,将左指针向右移动一位left++;} else {// sum大于目标值,将右指针向左移动一位right--;}}// 没有找到满足条件的两个数,返回空数组return NULL;
}int compare(const void* a, const void* b) {// 用于qsort排序的比较函数return (*(int*)a - *(int*)b);
}

说明:
twoSum 函数接受三个参数:指向整数数组 nums 的指针、数组的大小 numsSize 和目标值
target;它返回一个指向整数数组的指针,该数组包含两个数的索引,从给定数组中的两个数之和等于目标值。 twoSum 内部首先调用
qsort 函数对数组进行升序排序,这里使用了自定义的 compare 比较函数。 初始化左右指针 left 和 right
分别指向数组的起始位置和结束位置。 使用 while 循环进行迭代,当左指针小于右指针时,执行以下操作: 计算左右指针对应元素的和 sum。
如果 sum 等于目标值 target,创建一个大小为 2 的动态整型数组 result,将左右指针的值分别赋给 result[0] 和
result[1],然后返回 result。 如果 sum 小于目标值 target,将左指针向右移动一位。 如果 sum 大于目标值
target,将右指针向左移动一位。 如果结束循环后仍未找到满足条件的两个数,返回 NULL 表示未找到。 compare
是用于升序排序的比较函数,用于传递给 qsort 函数。 请注意,在使用完返回的结果后,务必使用 free函数释放动态分配的内存,防止内存泄漏。

Python3版本
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:# 对数组进行排序nums.sort()left = 0  # 左指针right = len(nums) - 1  # 右指针while left < right:# 当前左右指针对应元素之和sum = nums[left] + nums[right]if sum == target:# 找到目标值,返回对应的数组下标return [left, right]elif sum < target:# sum小于目标值,将左指针向右移动一位left += 1else:# sum大于目标值,将右指针向左移动一位right -= 1# 没有找到满足条件的两个数,返回空数组return []

说明:
首先使用 nums.sort() 对数组进行排序。 初始化左指针 left 指向数组的起始位置,右指针 right指向数组的结束位置。 使用 while 循环迭代,当左指针小于右指针时: 计算当前左右指针对应元素之和。 如果和等于目标值
target,则返回包含左右指针的列表。 如果和小于目标值 target,将左指针向右移动一位。 如果和大于目标值
target,将右指针向左移动一位。 如果循环结束后仍然没有找到满足条件的两个数,返回一个空数组。

复杂度分析

  • 时间复杂度:O(n log n),该解法的时间复杂度取决于排序算法的时间复杂度,其中n表示数组的长度
  • 空间复杂度:O(1),只需要常数级的额外空间。请确保在使用完结果后释放动态分配的内存

总结

解法思路优点缺点时间复杂度空间复杂度
暴力法使用两层循环遍历所有可能的组合,找到符合要求的组合简单直观,易于理解和实现时间复杂度高,需要遍历所有可能的组合O(n^2)O(1)
哈希表遍历数组,使用哈希表记录每个数的索引,查找目标值减去当前数的结果是否存在时间复杂度低,只需遍历一次数组需要额外的空间来存储哈希表O(n)O(n)
双指针法将数组排序后使用左右指针进行查找,根据和与目标值的大小关系不断移动指针时间复杂度低,只需遍历一次数组需要对数组进行排序,改变原始数组的顺序O(n log n)O(1)

相似题目

题目描述难度LeetCode链接
三数之和(3Sum)在给定整数数组中寻找所有不重复的三元组,使得它们的和为0中等LeetCode 15
四数之和(4Sum)在给定整数数组中寻找所有不重复的四元组,使得它们的和为目标值中等LeetCode 18
两数之和 II - 输入有序数组(Two Sum II - Input array is sorted)在有序整数数组中寻找两个数,使得它们的和等于目标值简单LeetCode 167
两数之和 III - 数据结构设计(Two Sum III - Data structure design)设计一个类,支持在一个整数数组中寻找两个数的和等于目标值简单LeetCode 170
两数之和 IV - 输入BST(Two Sum IV - Input is a BST)判断给定二叉搜索树中是否存在两个数的和等于目标值简单LeetCode 653

这篇关于【经典算法】LeetCode1:两数之和(Java/C/Python3实现含注释说明,Easy)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/864546

相关文章

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展,动画效果已经成为了网页设计中不可或缺的一部分,本文将深入探讨animation.css的工作原理,如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs

Spring Boot项目打包和运行的操作方法

《SpringBoot项目打包和运行的操作方法》SpringBoot应用内嵌了Web服务器,所以基于SpringBoot开发的web应用也可以独立运行,无须部署到其他Web服务器中,下面以打包dem... 目录一、打包为JAR包并运行1.打包为可执行的 JAR 包2.运行 JAR 包二、打包为WAR包并运行

Java进行日期解析与格式化的实现代码

《Java进行日期解析与格式化的实现代码》使用Java搭配ApacheCommonsLang3和Natty库,可以实现灵活高效的日期解析与格式化,本文将通过相关示例为大家讲讲具体的实践操作,需要的可以... 目录一、背景二、依赖介绍1. Apache Commons Lang32. Natty三、核心实现代

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Spring Boot 常用注解整理(最全收藏版)

《SpringBoot常用注解整理(最全收藏版)》本文系统整理了常用的Spring/SpringBoot注解,按照功能分类进行介绍,每个注解都会涵盖其含义、提供来源、应用场景以及代码示例,帮助开发... 目录Spring & Spring Boot 常用注解整理一、Spring Boot 核心注解二、Spr

SpringBoot实现接口数据加解密的三种实战方案

《SpringBoot实现接口数据加解密的三种实战方案》在金融支付、用户隐私信息传输等场景中,接口数据若以明文传输,极易被中间人攻击窃取,SpringBoot提供了多种优雅的加解密实现方案,本文将从原... 目录一、为什么需要接口数据加解密?二、核心加解密算法选择1. 对称加密(AES)2. 非对称加密(R

基于Go语言实现Base62编码的三种方式以及对比分析

《基于Go语言实现Base62编码的三种方式以及对比分析》Base62编码是一种在字符编码中使用62个字符的编码方式,在计算机科学中,,Go语言是一种静态类型、编译型语言,它由Google开发并开源,... 目录一、标准库现状与解决方案1. 标准库对比表2. 解决方案完整实现代码(含边界处理)二、关键实现细

详解如何在SpringBoot控制器中处理用户数据

《详解如何在SpringBoot控制器中处理用户数据》在SpringBoot应用开发中,控制器(Controller)扮演着至关重要的角色,它负责接收用户请求、处理数据并返回响应,本文将深入浅出地讲解... 目录一、获取请求参数1.1 获取查询参数1.2 获取路径参数二、处理表单提交2.1 处理表单数据三、

python通过curl实现访问deepseek的API

《python通过curl实现访问deepseek的API》这篇文章主要为大家详细介绍了python如何通过curl实现访问deepseek的API,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编... API申请和充值下面是deepeek的API网站https://platform.deepsee