This is the 16th day of my participation in the Gwen Challenge.More article challenges

For a better tomorrow, keep brushing LeetCode!

The title

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 <= 109Copy the code

The enumeration of violence

Their thinking

Using nested loops, the first loop starts at subscript 0 and the second loop starts at subscript +1 of the first loop. Each loop determines whether the sum of the two numbers equals target.

code

func twoSum(nums []int, target int) []int {
    for i, n1 := range nums {
        for j := i+1; j < len(nums); j++ {
            if n1 + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}
Copy the code

The execution result

Execution time: 40 ms beat 5.72% of users in all Go commits memory consumption: 3.6 MB beat 38.74% of users in all Go commitsCopy the code

Complexity analysis

  • Time complexity:O(N2), 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).

Hash table – Optimal solution

Their thinking

In solution one, we get x in the first loop, y in the second loop, and determine if x + y is equal to target, so we want to find target-x, so we can use a hash table to store the element, and get x in each loop, If x + y = target (x + y = target) = target (x + y = target)

code

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, n := range nums {
        if j, found := m[target-n]; found {
            return []int{j, i}
        }
        m[n] = i
    }
    return nil
}
Copy the code

The execution result

Execution time: 8 ms beat 37.21% of users in all Go commits memory consumption: 4.2 MB beat 10.15% of users in all Go commitsCopy the code

Complexity analysis

  • Time complexity:O(N), where N is the number of elements in the array. For each elementx, we can order 1 of thetaHash table) to findtarget - x.
  • Space complexity:O(N), where N is the number of elements in the array. Mainly the overhead of the hash table.

Topic link

Leetcode-cn.com/problems/tw…