Topic Description:

The original address

Given an integer array nums and an integer target, find the two integers in the array whose sum is the target value and return their array indices.

You can assume that there is only one answer for each input. However, you cannot use the same element in an array twice.

You can return the answers in any order.

The sample a

Input: nums = [2,7,11,15], target = 9 output: [0,1] description: because nums[0] + nums[1] == 9, return [0,1].Copy the code

Example 2

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

Example 3

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

prompt

  • 2 <= nums.length <= 103
  • –
    1 0 9 10^9     <= nums[i] <=
    1 0 9 10^9
  • –
    1 0 9 10^9     <= target <=
    1 0 9 10^9
  • There can only be one valid answer

Thought analysis

The enumeration of violence

As the algorithm meng new I come up is a bold idea, this is not simple, pa pa 2 for loop is not a problem to solve, the beauty of its violence enumeration

Although I also know this kind of problem, the first response is certainly not the optimal solution, but it is not impossible to use ha ha 😊

Complexity analysis

Time complexity: O(N2)O(N^2)O(N2), where N is the number of elements in the array. In the worst case any two numbers in the array have to be matched once.

Space complexity: O(1)O(1)O(1)

Hash table

To tell the truth, as the first normal algorithm in life, this solution or I saw the official solution to understand, haha

Here’s the official word

The time complexity of the violence enumeration is high because of the time complexity of finding target-x. Therefore, we need a better way to quickly find out if the target element is present in the array. If it exists, we need to find its index.

Using a hash table, you can reduce the time complexity of finding target-x from O(N)O(N)O(N) O(N) to O(1)O(1)O(1) O(1).

So we create a hash table, and for each x, we first query for the presence of target-x in the hash table, and then insert x into the hash table, ensuring that x does not match itself.

Complexity analysis

Time complexity: O(N)O(N)O(N), where N is the number of elements in the array. For each element x, we can find target – x in order (1).

Space complexity: O(N)O(N)O(N), where N is the number of elements in the array. Mainly the cost of the hash table.

AC code

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map : MutableMap<Int.Int> = mutableMapOf()
        for (i in nums.indices){
            val other =  target - nums[i]
            if (map.containsKey(other)){
                returnintArrayOf(map[other]!! ,i) } map[nums[i]] = i }throw IllegalArgumentException("no such answer")}}Copy the code

conclusion

Look at the submission records, half a year ago, that is to say, waste half a year, has been said to brush algorithm, into dafa, but each time is a whim to brush two, has not been calm down to seriously to do this thing. This time taking advantage of the gold mining activities, it is a flag again, this year brush 120. Cow force will not blow, I hope this year’s year-end summary of the time not to hit the face.

This article is participating in the “Nuggets 2021 Spring Recruiting activity”, click to see the details of the activity