This is the first day of my participation in Gwen Challenge

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

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 order of valid answers: can you come up with an algorithm whose time complexity is less than O(n2)?

Violent solution

I iterate over the array; J iterates from I +1 over the rest to see if it can find an element equal to target-nums[I].

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] === target - nums[i]) {
        return [i, j];
      }
    }
  }
  return [];
};
Copy the code

Hash table solution

Maintain a hash table, key is the number, value is the subscript, traverses the number group, determine whether (target value – current number) value exists in the hash table, if it does, return the corresponding subscript, does not exist, put the current number into the hash table

Code:

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {  
    // Save numbers => subscript key-value pairs
    let hashMap = new Map(a);for (let i = 0; i < nums.length; i++) {
        const another = target - nums[i];
        const isHas = hashMap.has(another);
        if (isHas) {
          return [hashMap.get(another), i];
        }
        hashMap.set(nums[i], i);
    }
    return [];
};
Copy the code

The complexity of the

  • Time complexity O(N)
  • Space complexity O(N)

A little thought:

It’s important to write variable names. Sometimes a line or two is fine, but readability is important, not simplicity.

We spend 90% of our time looking at code and 10% of our time writing it, and the readability of your code directly determines your and your colleagues’ mood each day. Writing code is like writing sentences. The code is easy to read and easy to understand. The next time you look at it, there will be no “what I wrote at that time, how can I not understand”.