Problem description

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:

Input: nums = [2,7,11,15], target = 9 output: [0,1]

Example 2:

Input: nums = [3,2,4] target = 6 output: [1,2] example 3:

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

Tip:

2 <= nums.length <= 104-109 <= nums[I] <= 109-109 <= target <= 109 there will only be one valid answer progression: Can you think of an algorithm whose time complexity is less than O(n2)?

Source: LeetCode link: leetcode-cn.com/problems/tw…

Method one: enumeration of violence

Ideas and Algorithms

The easiest way to think about it is to enumerate each number x in the array and find if target-x exists in the array.

When we look for target-x by walking through the array, we notice that every element before x has already been matched to x, so we don’t need to match any more. Each element can’t be used twice, so we just look for target-x in the element after x.

code

package com.burns.study.leetcode.learning.chapter1;/**
 * Created by burns.
 *
 * @author <a href="http://www.esoon-soft.com/">burns</a>
 * @date2021/07/03 8:11 * /

/** ** *@ClassName TwoSum
 * @Author Burns
 * @DAte2021/7/3 8:11 * /
public class TwoSum_1 {
    public static void main(String[] args){
        int[] nums = {2.7.11.15};
        int target = 17;
        int[] ints = twoSum(nums, target);

        StringBuilder sb = new StringBuilder("Search result subscript:");
        for (int i=0; i<ints.length; i++){ sb.append(ints[i]+"、");
        }
        System.out.println(sb);

    }
    public static int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        // The first layer loops from 0 to nums.length-1
        for (int i = 0; i < n; ++i) {
            // The second loop subscript starts from the next number in the first loop to nums.length-1
            // the same element in the array cannot be repeated in the answer.
            //tips:2, the second loop does not start with the subscript 0, because: 1, increase the number of loops, i.e. increase the time complexity 2, need to increase the judgment I! [0,3], [3,0], [3,0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0
            for (int j = i + 1; j < n; ++j) {
                // Determine if the values of the first and second loops add up to the target value
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j}; }}}return new int[0]; }}Copy the code

Output result:

Complexity analysis

Time complexity:

O(N^2) where N is the number of elements in the array. In the worst case, any two numbers in the array must be matched once.

Space complexity:

The O (1).

Method two: hash table

Ideas and Algorithms

Notice that the time complexity of method 1 is higher because the time complexity of finding target-x is too high. Therefore, we need a better way to quickly find out if there is a target element in an array. If it exists, we need to find its index. Using a hash table, you can reduce the time complexity of finding target-x from O(N) to O(1).

So we create a hash table, and for each x, we first check if target-x exists in the hash table, and then we insert x into the hash table to ensure that x doesn’t match us.

code

package com.burns.study.leetcode.learning.chapter1;/**
 * Created by burns.
 *
 * @author <a href="http://www.esoon-soft.com/">burns</a>
 * @date2021/07/03 8:11 * /

import java.util.HashMap;
import java.util.Map;

/** hash table *@ClassName TwoSum
 * @Author Burns
 * @DAte2021/7/3 8:11 * /
public class TwoSum_2 {
    public static void main(String[] args){
        int[] nums = {2.7.11.15};
        int target = 17;
        int[] ints = twoSum(nums, target);

        StringBuilder sb = new StringBuilder("Search result subscript:");
        for (int i=0; i<ints.length; i++){ sb.append(ints[i]+"、");
        }
        System.out.println(sb);

    }
    public static int[] twoSum(int[] nums, int target) {
        // Define a hashmap where key holds each nums value and value holds the subscript of each NUMs value
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        // Iterate through nums from beginning to end
        for (int i = 0; i < nums.length; ++i) {
            // Check if there is a target- current number in the map, return if there is, if not, insert into the map.
            if (hashMap.containsKey(target - nums[i])) {
                return new int[]{hashMap.get(target - nums[i]), i};
            }
            hashMap.put(nums[i], i);
        }
        return new int[0]; }}Copy the code

Complexity analysis

Time complexity:

O(N), where N is the number of elements in the array. For each element x, we can look O(1) for target-x.

Space complexity:

O(N), where NN is the number of elements in the array. Mainly the overhead of the hash table.

Author: Leetcode-Solution Link: leetcode-cn.com/problems/tw…