Topic describes

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer.

You can return the answers in any order.

Example 1:

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

Output: [0, 1]

Because nums[0] + nums[1] == 9, return [0, 1]

Example 2:

Enter: nums = [3,2,4], target = 6

Output: [1, 2]

Example 3:

Enter: nums = [3,3], target = 6

Output: [0, 1]

Tip:

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

There can only be one valid answer

Advanced: Can you think of an algorithm whose time complexity is less than O(n2)?

Source: LeetCodeLeetcode-cn.com/problems/tw…

title

Analysis of methods of violence

Seeing this kind of element finding problem, the first thing that comes to mind is brute force cracking, also known as loop traversal.

Now let’s look at the problem, how to use the brute force method to achieve.

The elements in the array are first iterated, assuming that the current iterated element nums[I] has a value of X, then the rest of the array needs to be iterated to see if there are any target-x numbers. If so, return the index corresponding to x and target-x; If there is no target-x number, then there is no nums[I] number, and the +1 operation should be performed on I to continue through the next element. Until we find the number we’re looking for. If we don’t find the number in the entire array, we don’t find the number in the entire array.

Step analysis:

Nums.length-1; nums.length-1; nums.length-1

2, layer 2 loop from I +1 — array length (nums.length)

3. At the first level of the loop, identify an element and then determine the matching element value (anotherNumber).

In the second loop, find the element matching the first loop and assign its subscript to the return array (result).

Hash method parsing

The previous solution can be realized, but the time complexity is relatively high. Is there a better method?

Let’s look at how this can be done using a Hash method.

We can use HashMap to find the corresponding element in O(1) time by taking the value of the array as the key and the index as the value. We can create a hash table, and for each x, we first check to see if target-x exists in the hash table, and if it doesn’t, we insert x into the hash table to ensure that x doesn’t match us. If target-x exists in the hash table, fetch the value and return it.

Step analysis:

First, we need to specify that the loop starts from 0 — array length (nums).

2. Loop to find the target value of the element pair. If there is no target value, add it to the map

3, If there is a target value, then assign it and its index to the return array (result).

Code implementation

Violent method code implementation

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for(int i=0; i<nums.length-1; i++){int anotherNumber = target - nums[i];
            for(int j=i+1; j<nums.length; j++){if(anotherNumber==nums[j]){
                    result[0] = i;
                    result[1] = j; }}}returnresult; }}Copy the code

Hash method code implementation

class Solution {
   public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        map.put(nums[0].0);
        for(int i=1; i<nums.length; i++){int anotherNumber = target - nums[i];
            if(map.get(anotherNumber)! =null){
                result[0] = map.get(anotherNumber);
                result[1] = i;
            }
            map.put(nums[i],i);
        }
        returnresult; }}Copy the code