Listen to the sediment spread… Pay attention to wechat public number [Chen PI’s JavaLib], help you give up the path of programming!

An algorithm problem every day, explain their own problem-solving ideas and implementation; You are welcome to comment or give your thoughts on how to solve the problem; Also can comment want me to explain which problem!

The title

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

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

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]

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

A, thinking

We all know that the SUM of two numbers, A+B=SUM. If you know SUM, and then you get an A, all you have to do is find something equal to SUM minus A.

For an array, if we go through the algorithm of adding two to two, that is, for each number in the array, we add it to the other numbers to see if it is equal to the target value, it is very slow, that is, O(N ^ 2) time.

On the other hand, as long as the number traversed and its corresponding index can be stored by some rule or algorithm (the rule and algorithm should be simple and fast), and we can find the number quickly afterwards, then the algorithm speed will be greatly improved. That’s just going to go through the array once, order N time.

For fast access and the ability to store the corresponding number and subscript key-value pairs, the hash table HashMap is the best choice.

Algorithm steps:

  1. Each num of the number group is iterated, and another addend A is calculated by target-num.
  2. Check whether key is equal to the value of A in the map. If so, return the subscript of the current number and the subscript of A.
  3. If num does not exist, place num in the map. The key is num and the value is the subscript of num in the array.

Second, algorithm implementation

package com.nobody;

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

/ * * *@DescriptionGiven an integer array nums and an integer target value target, find the two integers in the array and the target values and return their array subscripts. * You can assume that there is only one answer for each type of input. However, the same element in an array cannot be used twice. You can return the answers in any order. * Original link: https://leetcode-cn.com/problems/two-sum/ *@Author Mr.nobody
 * @Date 2021/1/21
 * @Version1.0 * /
public class TwoSum {

    public static int[] twoSum(int[] nums, int target) {

        // Log each iterated number, using the HashMap insert to find efficient time complexity of 0(1)
        Map<Integer, Integer> indexMap = new HashMap<>(16);

        // iterate over each number
        for (int index = 0; index < nums.length; index++) {
            // target-nums[index] calculates another addend and then looks for it in the map
            if(indexMap.get(target - nums[index]) ! =null) {
                // If found, return the subscripts of 2 addends
                return new int[] {indexMap.get(target - nums[index]), index};
            } else {
                // If no key is found, place the number in the map with key and value as its subscriptindexMap.put(nums[index], index); }}return null;
    }

	/ / test
    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[] {1.2.6.4.10.11.8.9}, 16))); }}Copy the code


Output result:

[2.4]
Copy the code

Leetcode execution result:

Three, the upper and lower chapters

LeetCode – add two numbers with algorithm