preface

Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

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.

Method 1 :(violence method)

The first object refers to the ith object, and the second object iterates through everything after “I” to see if it equals target.

Pseudo code

Funtion twoSum(NUMS, Target): For I ← 0 to (NUMs. length-1): for J ← (I + 1) to (NUMs. length-1): if target == nums[i] + nums[j]: return [i,j];Copy the code

Algorithm complexity analysis

  • Time complexity
  1. 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.
  2. Space complexity: O(1).

The execution result

Method 2 :(borrow a hash table)

  1. First, hash table is used to match the subscripts and values of the array.
  2. Iterate over each element in the array, subtracting the iterated element with the target value and assigning the result to the anotherNum variable.
  3. If the hash table contains the key anotherNum, and the value of this variable is a different index than the index of the element being traversed, the index of the traversed element and the index of the anotherNum element are returned.

Pseudo code

function twoSum(nums,target): result = []; Map = new map (); Set (nums[j],j); // Instantiate a HashMap object for J ← 0 to (nums.length-1): map.set(nums[j],j); For I ← 0 to (num. Length-1): anotherNum = target-nums [I]; // If the map contains anotherNum and its subscript is not equal to I, store the subscripts of I and anotherNum in the result array, and return break; return result;Copy the code

Algorithm 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.