Java implements LeetCode (1. Sum of two numbers)

Given an array of integers and a target value, find out the two numbers in the array that are the target values.

You can assume that each input corresponds to only one answer, and the same elements cannot be reused.

Example:

Given nums = [2, 7, 11, 15], target = 9

Because nums [0] + nums [1] = 2 + 7 = 9

So [0, 1] is returned

Idea 1: The most direct thinking, two traversal queries, time complexity O (N*N).

Code:

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;
	}

Idea 2: Sort first, then two pointers i, j and i start from the front, and j start from the back, when nums [i] + nums [j] > When target, j--; When nums [i] + nums [j] < When target, i + +; Note that after sorting, the previous subscript number has changed. Time Complexity O (N*Log2N)

Code:

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;
	}

Idea 3: Using space for time, using hashmap to store array structure, key as value and value as subscript. Time complexity O (N).

Code:

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 Address: https://github.com/xckNull/Algorithms-introduction