The sum of two Numbers

Leetcode-cn.com/problems/tw…

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]


Java algorithm

Ideas:

  • Error: thought to be an ordered array, trying to use target to shorten the numS array length, then using a subtraction traversal
  • Successful ideas
    1. Use HashMap to store subscript index and the difference from target
    2. Nums traversal: Checks whether the data whose difference value is the same as the current traversal value has been stored before storage
    3. In fact, the same element in the array can not be used twice the implicit hint to operate on the difference
package sj.shimmer.algorithm;

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

/** * Created by SJ on 2021/1/25. */
class D1 {
    public static void main(String[] args) {
        int[] nums = new int[] {3.2.4};
        int target = 6;
        int[] results = twoSum(nums, target);
        for (int i = 0; i < results.length; i++) {
            System.out.println(i + "="+ results[i]); }}/** * select * from index (int), ** from target (int), ** from target (int)@param nums
     * @param target
     * @return* /
    public static int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return nums;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() == nums[i]) {
                    return new int[]{entry.getKey(), i}; }}int value = target - nums[i];
            map.put(i, value);
        }
        returnnums; }}Copy the code

The official solution

  1. The enumeration of violence

Compare each number x to see if there is target-x

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: O(1).

  1. Hash table, which is the way I do it, but officially uses the difference as the key and the subscript as the value

    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 N is the number of elements in the array. Mainly the overhead of the hash table.