Java實現LeetCode的方法

小編給大家分享一下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;
	}

以上是“Java實現LeetCode的方法”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！