1. Sum of two numbers. Given an array of integers, returns the index of two numbers such that they add up to a specified target value. You can assume that every input has at least one solution, and you can’t use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].Copy the code

The first was a false attempt

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] testNums = new int[nums.length];
        int j = 0;
        for (int i=0; i<nums.length; i++){if(nums[i]<target){
                testNums[j] = nums[i];
                j=j+1; }}for(int l=0; l<j; l++){for(int k=l+1; k<j; k++){if(testNums[l]+testNums[k]==target){
                    return new int[]{l,k}; }}}return null; }}Copy the code

Wrong!!

This method is used to obtain the sequence number of our custom array, not the required sequence number. Later a more serious problem was discovered. He did not say that there could be no negative numbers ！！！！ There is no need to determine whether the values in the array are greater than and…

And then we reimagine it, and we do a basic solution

Method one: Cycle of violence

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i=0; i<nums.length; i++){for(int k=i+1; k<nums.length; k++){if(nums[i]+nums[k]==target){
                    return new int[]{i,k}; }}}throw new IllegalArgumentException("No two sum solution"); }}Copy the code

As for the results, even the simplest ones are not very efficient.

The efficiency of

The principle of analyzing this method is simple: each value is iterated over the other values to see if anything matches the condition. For (int k= I +1; k

Method 2: Iterate the hash table twice

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

You can see a big improvement in efficiency.

The efficiency of

The principle of analyzing this method is to use the Hash table to replace the cost of time with the cost of space, turning a loop of O(n) complexity into a lookup that is close to O(1). Why close? Because if the hash table has a lot of collisions, the complexity will move toward O(n). We store the value of each element in the array as a key in the Hash table, and store its serial number as the corresponding value in the Hash table. Then we search through the number group to see if there is a corresponding value in the key of the Hash table, and extract the corresponding value of the key if there is. Time complexity: O(n) Space complexity: O(n)

Method 3: Iterate the Hash table once

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

Efficiency has improved slightly. But some of it is unacceptable. Why is it still just in the middle… Then I tried it a few times and it hovered around 40% to 50%. Why so fast? Theoretically, you need to loop through the results at least once, which is order n.

The efficiency of

Analyzing the principle of this method is actually an improvement of method 2, because we don’t need to put all the arrays into the hash table, we just want to get the sequence number of two values that add up to the target number, so we compare the values in the array when we put them into the hash table. End the loop as soon as you get the desired value. Time complexity: O(n) Space complexity: O(n)

If you have a better idea or another comment on my description here, please contact me. thank you

More github.com/LeonChen102…