Java實(shí)現(xiàn)LeetCode（1.兩數(shù)之和）
給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù)。
你可以假設(shè)每個(gè)輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]
思路一：最直接的思維，兩次遍歷查詢，時(shí)間復(fù)雜度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;
}
思路二：先排序，然后兩個(gè)指針i,j，i從前開始，j從后開始查找，當(dāng)nums[i]+nums[j]>target時(shí)，j--；當(dāng)nums[i]+nums[j]<target時(shí)，i++；注意排序后，之前的下標(biāo)數(shù)字已經(jīng)變化了。時(shí)間復(fù)雜度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;
}
思路三：利用空間換時(shí)間方式，用hashmap存儲(chǔ)數(shù)組結(jié)構(gòu)，key為值，value為下標(biāo)。時(shí)間復(fù)雜度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
到此這篇關(guān)于Java實(shí)現(xiàn)LeetCode（兩數(shù)之和）的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)兩數(shù)之和內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
java.lang.ArrayStoreException異常的解決方案
這篇文章主要介紹了java.lang.ArrayStoreException異常的解決方案，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12
這篇文章主要針對Java基于Socket的文件傳輸案例進(jìn)行詳細(xì)解析，具有一定的參考價(jià)值，感興趣的朋友可以參考一下2016-02-02
SpringBoot整合RocketMQ實(shí)現(xiàn)消息發(fā)送和接收的詳細(xì)步驟
這篇文章主要介紹了SpringBoot整合RocketMQ實(shí)現(xiàn)消息發(fā)送和接收功能,我們使用主流的SpringBoot框架整合RocketMQ來講解，使用方便快捷，本文分步驟給大家介紹的非常詳細(xì)，需要的朋友可以參考下2021-08-08
Java操作Elasticsearch?rest-high-level-client?的基本使用
這篇文章主要介紹了Java操作Elasticsearch?rest-high-level-client?的基本使用,本篇主要講解一下?rest-high-level-client?去操作?Elasticsearch的方法，結(jié)合實(shí)例代碼給大家詳細(xì)講解，需要的朋友可以參考下2022-10-10
springcloud Zuul動(dòng)態(tài)路由的實(shí)現(xiàn)
這篇文章主要介紹了springcloud Zuul動(dòng)態(tài)路由的實(shí)現(xiàn)，詳細(xì)的介紹了什么是Zuu及其動(dòng)態(tài)路由的實(shí)現(xiàn)，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-11-11
JPA是Java Persistence API的簡稱，中文名Java持久層API，是JDK 5.0注解或XML描述對象－關(guān)系表的映射關(guān)系，并將運(yùn)行期的實(shí)體對象持久化到數(shù)據(jù)庫中。本文主要介紹了JPA如何設(shè)置默認(rèn)字段及其長度，感興趣的同學(xué)可以了解一下2021-12-12
springboot項(xiàng)目啟動(dòng)的時(shí)候,運(yùn)行main方法報(bào)錯(cuò)NoClassDefFoundError問題
這篇文章主要介紹了springboot項(xiàng)目啟動(dòng)的時(shí)候,運(yùn)行main方法報(bào)錯(cuò)NoClassDefFoundError問題,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01
這篇文章主要介紹了Spring事務(wù)的七種傳播行為，文章圍繞主題的相關(guān)資料展開詳細(xì)的內(nèi)容解說，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-04-04
Thymeleaf 3.0 自定義標(biāo)簽方言屬性的實(shí)例講解
這篇文章主要介紹了Thymeleaf 3.0 自定義標(biāo)簽方言屬性的實(shí)例講解，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09
spring/springboot整合curator遇到的坑及解決
這篇文章主要介紹了spring/springboot整合curator遇到的坑及解決方案，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-05-05