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存儲數(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)文章
@PathVariable、@RequestParam和@RequestBody的區(qū)別
本文主要介紹了@PathVariable、@RequestParam和@RequestBody的區(qū)別和使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05
Java+OpenCV實(shí)現(xiàn)人臉檢測并自動(dòng)拍照
這篇文章主要為大家詳細(xì)介紹了Java+OpenCV實(shí)現(xiàn)人臉檢測，并調(diào)用筆記本攝像頭實(shí)時(shí)抓拍，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-07-07
SpringBoot?+?Disruptor實(shí)現(xiàn)特快高并發(fā)處理及使用Disruptor高速實(shí)現(xiàn)隊(duì)列的過程
Disruptor是一個(gè)開源的Java框架，它被設(shè)計(jì)用于在生產(chǎn)者—消費(fèi)者（producer-consumer problem，簡稱PCP）問題上獲得盡量高的吞吐量（TPS）和盡量低的延遲，這篇文章主要介紹了SpringBoot?+?Disruptor?實(shí)現(xiàn)特快高并發(fā)處理，使用Disruptor高速實(shí)現(xiàn)隊(duì)列,需要的朋友可以參考下2023-11-11
Java中的stream流的概念解析及實(shí)際運(yùn)用總結(jié)
流是指傳輸時(shí)的數(shù)據(jù),Java為流準(zhǔn)備了很多內(nèi)置類,尤其是IO輸入輸出流非常常用,這里我們來看一下Java中的stream流的概念解析及實(shí)際運(yùn)用總結(jié)2016-06-06
Spring?Cloud?Feign?使用對象參數(shù)的操作
這篇文章主要介紹了Spring?Cloud?Feign?如何使用對象參數(shù)的問題，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-02-02
這篇文章主要介紹了Java 判斷數(shù)組是否相等的方法示例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
關(guān)于WeakhashMap與HashMap之間的區(qū)別和聯(lián)系
這篇文章主要介紹了關(guān)于WeakhashMap與HashMap之間的區(qū)別和聯(lián)系,WeakHashMap從名字可以得知主要和Map有關(guān),不過還有一個(gè)Weak,我們就更能自然而然的想到這里面還牽扯到一種弱引用結(jié)構(gòu),因此想要徹底搞懂,我們還需要知道四種引用,需要的朋友可以參考下2023-09-09
java實(shí)現(xiàn)字符串和日期類型相互轉(zhuǎn)換的方法
這篇文章主要介紹了java實(shí)現(xiàn)字符串和日期類型相互轉(zhuǎn)換的方法,涉及java針對日期與字符串的轉(zhuǎn)換與運(yùn)算相關(guān)操作技巧,需要的朋友可以參考下2017-02-02
這篇文章主要介紹了Spring maven filtering使用方法詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09
本篇文章主要介紹了springboot-controller的使用詳解，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-08-08