LeetCode两数之和
2024-10-19 16:06:59
LeetCode 两数之和
题目描述
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定nums = [2,7,11,15],target=9
因为nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1]
Java 解法
import java.util.HashMap;
/**
* @author zhkai
* @date 2021年3月23日14:27:28
*/
public class TwoNumSum {
private final static int NUM_NUMS = 2;
/**
* 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标
*
* @param nums 整数数组
* @param target 目标值
* @return 数组中和为目标值的两个整数的数组下标
*/
public static int[] twoNumSum(int[] nums, int target) {
int len = nums.length;
if (len < NUM_NUMS) {
return new int[0];
}
int[] result = new int[2];
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
}
}
}
return result;
}
/**
* 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标
*
* @param nums 整数数组
* @param target 目标值
* @return 数组中和为目标值的两个整数的数组下标
*/
public static int[] twoNumSumMap(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(16);
int len = nums.length;
for (int i = 0; i < len; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[0];
}
}
Java解法效率对比
输入:nums = {1, 3, 5, 7, 9, 12, 13, 19, 20};target = 23;
方法一:5074400ns
方法二:264300ns
Python 解法
from typing import List
def two_sum_dict(nums: List[int], target: int) -> List[int]:
"""
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标
:param nums: 整数数组
:param target: 目标值
:return: 数组中和为目标值的两个整数的数组下标
"""
dict_item = dict()
for i, num in enumerate(nums):
if target - num in dict_item:
return [dict_item[target - num], i]
return []
def two_sum(nums: List[int], target: int) -> List[int]:
"""
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标
:param nums: 整数数组
:param target: 目标值
:return: 数组中和为目标值的两个整数的数组下标
"""
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
Python解法效率对比
输入:nums = {1, 3, 5, 7, 9, 12, 13, 19, 20};target = 23;
方法一:10200ns
方法二:6800ns
最新文章
- HTML5快速入门(三)—— 标签综合运用
- 使用MJRefresh遇到的一个问题,上拉刷新后tableview瞬间滑到最底部
- c#跨线程访问控件帮助类
- Android 常用抓包工具介绍之Charles
- tab切换(修改)
- qq临时会话设置
- 【树状数组】CSU 1811 Tree Intersection (2016湖南省第十二届大学生计算机程序设计竞赛)
- python网络编程——将IPv4地址转换成不同的格式
- LoadTest中内存和线程Troubleshooting实战
- Visual Studio Package 插件开发之自动生成实体工具
- JS盒模型
- Docker Registry V2 Garbage Collection
- Mysql数据库如何创建用户
- OpenStack的架构详解(转)
- 面向对象OO第1-3次作业总结
- spring事务的隔离级别(透彻理解)
- timestamp和date及datetime的区别
- bzoj3473字符串&;bzoj3277串
- Java集合框架:Collections工具类
- PHP函数(四)-变量函数