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