Location>code7788 >text

Question 1 of the question bank: the sum of two numbers

Popularity：66 ℃/2025-03-01 16:51:06

The sum of two numbers

Question description

Given an integer array nums and an integer target value target, please find the two integers that are the target value target in the array and return their array subscript.

 You can assume that each input will only correspond to one answer, and that you cannot use the same element twice.

 You can return the answers in any order.

 Example 1:

 Input: nums = [2,7,11,15], target = 9
 Output: [0,1]
 Explanation: Because nums[0] + nums[1] == 9 , return [0, 1] .
 Example 2:

 Input: nums = [3,2,4], target = 6
 Output: [1,2]
 Example 3:

 Input: nums = [3,3], target = 6
 Output: [0,1]

 hint:

 2 <= <= 104
 -109 <= nums[i] <= 109
 -109 <= target <= 109
 There will only be one valid answer

 Advanced: Can you come up with an algorithm with a time complexity less than O(n2)?

Solutions

Violent Method - Loop Traversal - Time Complexity O(n2)

  1. Ideas
    This method is relatively simple, which is to solve the problem through two-layer loops. In the outer loop, we first subtract the current element with the value of the target, and then find the element equal to this difference in the inner loop, and get two offsets. Pay attention to the process of the cycle (PythonLanguage) Use offsets instead of directly looping on element values.

  2. Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            minus = target - nums[i]
            for j in range(i+1, len(nums)):
                if nums[j] == minus:
                    return [i, j]

Using hash table - time complexity O(n)

  1. Ideas
    We store the value of the key as each element in the nums array and store the value corresponding to the key as the index corresponding to the element. In this way, when the entire nums array is convenient, if target - the current elementIn hash table, then it means that two numbers that meet the meaning of the question have been found, and the offset is returned. If target - the current elementNot in the hash table, it means that the two numbers that meet the meaning of the question have not been found, and the value and index are stored in the hash table at this time. That is, {value: offset}, so that we can not only quickly find the number that meets the question's meaning, but also conveniently find the offset corresponding to the number, killing two birds with one stone.

  2. Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {}
        for offset, num in enumerate(nums):
            if target - num in map:
                return [offset, map[target - num]]
            else:
                map[num] = offset

Summarize

When we do the questions, we can first consider using the simplest violent solution to solve the problem, and then we can think about using a high-time efficiency method. If we really don’t have any ideas, we can check the boss’s solution, which will help improve our programming ability. Bye bye ~

<Previous Next>