Leetcode.windliang. cc/ first available

Topic Description (Easy Difficulty)

Given an array and a destination sum, take two numbers from the array and add them to the destination sum. Print the subscripts of the two numbers.

Method a

Just to make it simple, double loop, go through all the cases to see if the sum equals the target sum, if it matches the direct output.

public int[] twoSum1(int[] nums, int target) {
		int []ans=new int[2];
		for(int i=0; i<nums.length; i++){for(int j=(i+1); j<nums.length; j++){if(nums[i]+nums[j]==target){
					ans[0]=i;
					ans[1]=j;
					returnans; }}}return ans;
    }
Copy the code

Time complexity: Two-layer for loop, O (n²)

Space complexity: O (1)

Method 2

Look at the second for loop step in the above solution.

for(int j=(i+1); j<nums.length; j++){if(nums[i]+nums[j]==target){
Copy the code

Let’s look at it another way:

for(int j=(i+1); j<nums.length; j++){ sub=target-nums[i]if(nums[j]==sub){
Copy the code

The second for loop does nothing more than iterate over all the elements to see which one is equal to sub, in order n time.

Is there a way to find out if there’s an element equal to sub without going through it?

Hash table!!

We can store each element of the array as the hash key and the subscript as the hash value.

If sub is in the hash key, the time complexity is O (1)!

Note that you also need to make sure that the element you found is not the current element, because they say you can only use an element once.

public int[] twoSum2(int[] nums, int target) {
		Map<Integer,Integer> map=new HashMap<>();
		for(int i=0; i<nums.length; i++){ map.put(nums[i],i); }for(int i=0; i<nums.length; i++){int sub=target-nums[i];
			if(map.containsKey(sub)&&map.get(sub)! =i){return new int[]{i,map.get(sub)}; }}throw new IllegalArgumentException("No two sum solution");
	}
Copy the code

Time complexity: One less for loop than solution 1, reduced to O (n)

Space complexity: The so-called space change time is reflected here, creating a hash table, space complexity becomes O (n).

Method three

If we look at solution two, the two for loops, they look the same, so of course we can combine them. There’s no change in complexity, just that you don’t need to determine if it’s the current element, because it hasn’t been added to the hash yet.

public int[] twoSum3(int[] nums, int target) {
		Map<Integer,Integer> map=new HashMap<>();
	    for(int i=0; i<nums.length; i++){int sub=target-nums[i];
		    if(map.containsKey(sub)){
			    return new int[]{i,map.get(sub)};
		}
		map.put(nums[i], i);
	}
	throw new IllegalArgumentException("No two sum solution");
}
Copy the code

conclusion

The topic is relatively easy, after all, violent methods can also be solved. The only bright spot is when the time complexity drops from O (n ^ 2) to O (n), the application of hash feels like a big hit.