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