“This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

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]Copy the code

Example 2:

Input: nums = [3,2,4], target = 6Copy the code

Example 3:

Input: nums = [3,3], target = 6Copy the code

Tip:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • There can only be one valid answer

Advanced: Can you think of an algorithm whose time complexity is less than O(n2)?

Answer key 1

The simplest solution is O(n2)

We iterate over each element in the array, then match all the other elements in the array to determine if the sum of the two numbers equals target. If so, return true, otherwise continue

Since the question guarantees that there is a valid answer, the above process is guaranteed to find the result

The code is as follows:

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

The above code submission can be passed, which takes about 120ms, more than 32% of the submission. It can be seen that the problem solving efficiency of our version with time complexity of O(n2) is still relatively low, so let’s take a look at problem solving 2

Answer key 2

In solution 1, our efficiency is mainly lost in the inner loop. We need to find each element and add the current value of the outer loop to determine whether the result is equal to target

So let’s think about how do we optimize this search process?

The typical fast search algorithm is binary search. But the array we are given here is not an ordered array, and since we are required to return the subscripts of the elements that meet the criteria, if we sort nums, the subscripts must be changed

So we need to get the ordered array corresponding to the original array by sorting the array subscript. The code is as follows:

var twoSum = function(nums, target) { const len = nums.length, indArr = []; for(let i = 0; i<len; i++){ indArr[i] = i; } indArr. Sort ((a, b) = > nums [indArr [a]] - nums [indArr [b]]) return [0, 1]}Copy the code

Here, we first copy the subscript of the original array, and then use the sort method to obtain the value of the corresponding subscript position of the NUMS array by the corresponding value of the subscript array indArr, conduct size comparison, and sort the subscript of indArr, so that the subscript value of the sorted indArr corresponds to the value of the original array

Next we loop through each element in indArr, using the find function bisection to find the matched target value in the interval following the subscript position

The find function determines whether the found element is equal to the target value and returns the corresponding subscript if it is, or -1 otherwise

The loop determines whether the target value can be found in the current interval by judging the return value of the find function

The code is as follows:

Var twoSum = function(nums, target) {const len = nums.length, var twoSum = function(nums, target) {const len = nums.length, for(let i = 0; i<len; i++){ indArr[i] = i; } sort((a,b) => nums[indArr[a]]-nums[indArr[b]]) i<len-1; I ++){const ind = find(I +1,target-nums[indArr[I]]) if(ind>-1) return [indArr[I],indArr[ind]]} function  find(l,target){ let r = len-1; while(l<r){ const mid = (l+r) >> 1; If (nums[indArr[mid]]<target) l = mid+1 else r = mid} return nums[indArr[l]]===target l:-1 } };Copy the code

The above code submission is ok, it takes about 70ms, more than 80+% of the submission

If you have any questions or suggestions, please leave a comment!