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

到此这篇关于Java实现LeetCode(两数之和)的文章就介绍到这了,更多相关Java实现两数之和内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-06-28

vscode刷acm、leetcode的题目

目录 简介 编译器 Windows 使用 Code Runner 插件运行代码 使用 C/C++ 插件编译并调试 安装插件 配置编译 配置 GDB/LLDB 调试器 开始调试代码 简介 Visual Studio Code(以下简称 VS Code) 是一个由微软开发,同时支持 Windows.Linux 和 macOS 等操作系统且开放源代码的代码编辑器.它是用 TypeScript 编写的,并且采用 Electron 架构.它带有对 JavaScript.TypeScript 和 Node.

Java实现LeetCode(组合总和)

leetcode题目 组合总和 -- leetcode 39 题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的数字可以无限制重复被选取. 说明: 所有数字(包括 target)都是正整数. 解集不能包含重复的组合.  示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [   [7],   [2,2,3

Java实现LeetCode(报数)

题目如下: public String countAndSay(int n) { if(n == 1){ return "1"; } //递归调用,然后对字符串处理 String str = countAndSay(n-1) + "*";//为了str末尾的标记,方便循环读数 char[] c = str.toCharArray(); int count = 1; StringBuilder s = new StringBuilder(); for(int i =

Java实现LeetCode(螺旋矩阵)

LeetCode54. 螺旋矩阵 java实现 题目 难度 中 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素. 示例 1: 输入:  [   [ 1, 2, 3 ],   [ 4, 5, 6 ],   [ 7, 8, 9 ]  ]  输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入:  [    [1, 2, 3, 4],    [5, 6, 7, 8],    [9,10,11,12]  ] 输出: [1,2,3,4,8

如何用C++制作LeetCode刷题小技巧-错题记录本

一 . 刷题小技巧 1,c++中的for(auto a:b)用法 for(auto a:b)中b为一个容器,效果是利用a遍历并获得b容器中的每一个值,但是a无法影响到b容器中的元素. for(auto &a:b)中加了引用符号,可以对容器中的内容进行赋值,即可通过对a赋值来做到容器b的内容填充. 2,c++中map的元素进行按照值排序(默认按照键排序) 为什么不能对map进行按值排序呢?因为sort排序只能对线性结构进行排序,而map是采用红黑树的数据结构. 一是通过将map转换到序列容器,再用

如何在Intellij中安装LeetCode刷题插件方便Java刷题

一.安装 在 IDEA(2019)的 setting 的 Plugins 的 Marketplace 中搜索 leetcode,即可以找到该插件,安装完成了,重启即可. 二.配置 1.重启完成后,第一次使用的时候,需要一些基本的配制,在 setting 中的 Tools 中可以找到该插件工具,为 leetcode plugin,在里面,可以选择访问的为国际的 LeetCode 还是国内的,以及何种语言,同时,输入自己账户名(LoginName)和密码(Password),则可以和自己帐号关联起来

教你如何用C#制作文字转换成声音程序

教你如何用C#制作文字转换成声音程序 在System.Speech命名空间下,SpeechSynthesizer类可以把文字读出来,一起来玩下~~ 首先在Windows窗体项目中引入System.Speech.界面部分: 后台代码也很简单,只不过调用了SpeechSynthesizer类的一些方法: using System.Windows.Forms; using System.Speech; using System.Speech.Synthesis; namespace WindowsFo

使用Python制作一个打字训练小工具

一.写在前面 说道程序员,你会想到什么呢?有人认为程序员象征着高薪,有人认为程序员都是死肥宅,还有人想到的则是996和 ICU. 别人眼中的程序员:飞快的敲击键盘.酷炫的切换屏幕.各种看不懂的字符代码. 然而现实中的程序员呢?对于很多程序员来说,没有百度和 Google 解决不了的问题,也没有 ctrl + c 和 ctrl + v 实现不了的功能. 那么身为一个程序员,要怎么让自己看起来更加"专业"呢?答案就是加快自己的打字速度了,敲的代码可能是错的,但这个13却是必须装的! 然而还

如何基于Python制作有道翻译小工具

这篇文章主要介绍了如何基于Python制作有道翻译小工具,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 该工具主要是利用了爬虫,爬取web有道翻译的内容. 然后利用简易GUI来可视化结果. 首先我们进入有道词典的首页,并点击翻译结果的审查元素 之后request响应网页,并分析网页,定位到翻译结果. 使用tkinter来制作一个建议的GUI 期间遇到的一个问题则是如何刷新翻译的结果,否则的话会在text里一直累加翻译结果. 于是,在mainlo

17个Python小技巧分享

1.交换变量 复制代码 代码如下: x = 6 y = 5 x, y = y, x print x >>> 5 print y >>> 6 2.if 语句在行内 复制代码 代码如下: print "Hello" if True else "World" >>> Hello 3.连接 下面的最后一种方式在绑定两个不同类型的对象时显得很酷. 复制代码 代码如下: nfc = ["Packers",

VC小技巧汇总之5则实用小技巧

本文搜集汇总VC的5则小技巧,非常实用,对于VC程序设计有很好的参考借鉴价值,详情如下: 1.如何获取程序所在的路径 也就是获取你这个程序本身所在的路径. 在应用程序类CxxApp的头文件中定义一个变量CString m_exePath;用来放置程序的路径名,在应用程序类CxxApp的InitInstance()函数中加入如下语句: TCHAR m_Path[MAX_PATH]; GetModuleFileName( NULL, m_Path, MAX_PATH ); //获取程序路径(包括程序

详解React Native顶|底部导航使用小技巧

导航一直是App开发中比较重要的一个组件,ReactNative提供了两种导航组件供我们使用,分别是:NavigatorIOS和Navigator,但是前者只能用于iOS平台,后者在ReactNative0.44版本以后已经被移除了. 好在有人提供了更好的导航组件,就是我们今天要讲的react-navigation,并且ReactNative官方更推荐我们使用此组件. 本篇文章只讲解基础用法,如果你想了解更多,请戳这里->戳我.  简介 react-navigation主要包括导航,底部tab,

Docker配置容器位置与小技巧总结

Docker使用小技巧 1.清理全部停止的docker容器 有时候我们会有很多已经停止的容器或者由于错误强制退出不能用的容器,那我们就需要删除了,但是我们一个一个的rm删除很麻烦,有多少容器就要rm多少次,我们可以根据docker ps -qa 查出所有容器的id,一次性全部删除,不用担心会删除正在运行的容器,运行中的容器rm无法删除,这样我们就一次性把所有停止的容器删除了 # 只适用于Linux环境下 docker rm $(docker ps -qa) 2.查看镜像中得环境变量 当我们制作好

iOS组件依赖避免冲突的小技巧分享

问题缘由 本文以 YBImageBrowser[1] 组件举例. YBImageBrowser 依赖了 SDWebImage,在使用 CocoaPods 集成到项目中时,可能会出现一些依赖冲突的问题,最近社区提了多个 Issues 并且在 Insights -> Traffic -> Popular content 中看到了此类问题很高的关注度,所以不得不着手解决. 严格的版本限制 一个开源组件的迭代过程中,保证上层接口的向下兼容就不错了.为了优化性能并且控制内存,YBImageBrowser

AngularJS 整理一些优化的小技巧

关于优化ng的手段网上已经有很多了,核心都是从$$watchers这个作用域内部属性说起的,今天我来说点别的,本质还是不变的,因为这是ng的硬伤,不过我相信只要运用合适的手法,这些问题还是可以避免的. ng简介 angularjs简称ng,是google出品的mvvm框架,此在提高前端项目开发效率(实践中来看确实很能提高开发效率),以控制器,指令,服务来围绕整个项目,内部以独有的DI来解决三层之前的调用问题.更多的详情信息可以参考我之前写的ng源码分析. ng的硬伤 说到硬伤就要先说下它的简单的