Java实现LeetCode(1.两数之和)
作者:NullPointerExcept 发布时间:2021-06-03 02:11:19
标签:Java,LeetCode,两数之和
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]
思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N)。
代码:
public static int[] twoSum1(int[] nums, int target) {
int[] label = new int[2];
for(int i=0;i<nums.length-1;i++) {
int tmp = target - nums[i];
for(int j=i+1;j<nums.length;j++) {
if(tmp == nums[j]) {
label[0] = i;
label[1] = j;
}
}
}
return label;
}
思路二:先排序,然后两个指针i,j,i从前开始,j从后开始查找,当nums[i]+nums[j]>target时,j--;当nums[i]+nums[j]<target时,i++;注意排序后,之前的下标数字已经变化了。时间复杂度O(N*Log2N)
代码:
public static int[] twoSum2(int[] nums, int target) {
int[] label = new int[2];
int[] tmpArr = new int[nums.length];
for(int i=0;i<nums.length;i++) {
tmpArr[i]=nums[i];
}
Arrays.sort(nums);
int i=0;
int j=nums.length-1;
while (i<j) {
if(nums[i]+nums[j]==target) {
label[0] = nums[i];
label[1] = nums[j];
break;
}else if(nums[i]+nums[j]>target){
j--;
}else {
i++;
}
}
for(int k=0;k<tmpArr.length;k++) {
if(tmpArr[k]==label[0]) {
label[0]=k;
}
if(tmpArr[k]==label[1]) {
label[1]=k;
}
}
return label;
}
思路三:利用空间换时间方式,用hashmap存储数组结构,key为值,value为下标。时间复杂度O(N)。
代码:
public static int[] twoSum3(int[] nums, int target) {
int[] label = new int[2];
HashMap<Integer, Integer> hashMap = new HashMap<>();
for(int i=0;i<nums.length;i++) {
hashMap.put(nums[i], i);
}
for(int i=0;i<nums.length;i++) {
if(hashMap.containsKey(target-nums[i])&&hashMap.get(target-nums[i])!=i) {
label[0] = i;
label[1] = hashMap.get(target-nums[i]);
break;
}
}
return label;
}
github地址:https://github.com/xckNull/Algorithms-introduction
来源:https://blog.csdn.net/jek123456/article/details/79989145
0
投稿
猜你喜欢
- 前言LocalDateTime、LocalDate、LocalTime 是 Java8 全新的日期框架,加强了对时间的管理,有很多特别好用的
- java的jar是一个打包工具,用于将我们编译后的class文件打包起来,这里面主要是举一个例子用来说明这个工具的使用。在C盘下的temp文
- Spring Cloud feign GET请求无法用实体传参代码如下:@FeignClient(name = "eureka-c
- java.sql.Timestamp(时间戳)继承父类:java.util.Date所有已实现的接口:Serializable, Clone
- 前言Spring是一个开源框架,Spring是于2003 年兴起的一个轻量级的Java 开发框架,由Rod Johnson 在其著作Expe
- 在 Spring 容器中,两个 Bean 之间除了通过 <ref> 建立依赖关系外,还存在着一些特殊关系。1 继承在
- Spring 配置文件报错:元素 "context:component-scan" 的前缀 "context&
- 配置不生效的解决办法注意:如果配置不生效,则说明spring优先加载了其他配置:解决办法:添加启动参数 -Dlogging.config=c
- Java8 HashMap键与Comparable接口最容易使 HashMap 发生哈希冲突的方法是什么呢?我们可以创建一个类,让它的哈希函
- 前言为什么用动静态库我们在实际开发中,经常要使用别人已经实现好的功能,这是为了开发效率和鲁棒性(健壮性);因为那些功能都是顶尖的工程师已经写
- 我们首先看下BASEJDBC的写法实例:package com.dao;import java.sql.Connection;import
- seata-1.4.0安装及使用 1、简介Seata 是一款开源的分布式事务解决方案,致力于提供高性能和简单易用的分布式事务服务。
- 在Java中有两类线程:User Thread(用户线程)、Daemon Thread(守护线程) 用个比较通俗的比如,任何一个守
- 前言 实际业务开发中,集合的判断和操作也是经常
- 本文实例讲述了Java接口的简单定义与实现方法。分享给大家供大家参考,具体如下:1、接口是Java中最终要的概念,接口可以理解为一种特殊的类
- Java基础面试题及答案集锦(基础题122道,代码题19道),具体详情如下所示:1、面向对象的特征有哪些方面1.抽象:抽象就是忽略一个主题中
- 一、安装MongoDB4.0.3(××)1.1、官方安装文档https://docs.mongodb.com/manual/tutorial
- 面试题1:说一下抽象类和接口有哪些区别?正经回答:抽象类和接口的主要区别:从设计层面来说,抽象类是对类的抽象,是一种模板设计;接口是行为的抽
- 在笔试编程过程中,关于数据的读取如果迷迷糊糊,那后来的编程即使想法很对,实现很好,也是徒劳,于是在这里认真总结了Java Scanner 类
- 讲这个例子前,咱们先来看一个简单的程序:字符串数组实现数字转字母:#include <stdio.h>#include <