Location>code7788 >text

leetcode001 The sum of two numbers

Popularity：473 ℃/2025-04-13 22:11:13

Problem description: sum of two numbers

Given an array of integersnumsand an integer target valuetarget, please find it in this arrayand is the target valuetargetThattwoInteger and return their array subscript.

You can assume that each input will only correspond to one answer, andCannot reuse the same elements. The answers can be returned in any order.

Example

Example 1

  • enter: nums = [2,7,11,15], target = 9
  • Output: [0,1]
  • explain: becausenums[0] + nums[1] == 9,return[0, 1]。

Example 2

  • enter: nums = [3,2,4], target = 6
  • Output: [1,2]
  • explain: nums[1] + nums[2] == 6,return[1, 2]。

Example 3

  • enter: nums = [3,3], target = 6
  • Output: [0,1]
  • explain: nums[0] + nums[1] == 6,return[0, 1]。

Constraints

  • 2 <= <= 10⁴
  • -10⁹ <= nums[i] <= 10⁹
  • -10⁹ <= target <= 10⁹
  • There will only be one valid answer

Advanced requirements

Can you come up with an algorithm with a time complexity of less than O(n²)?

Solutions

1. Brute Force

  • Time complexity: O(n²)
  • Space complexity: O(1)
  • Ideas：
    • Using a double loop, iterate through all possible combinations of two numbers.
    • Check if their sum is equal totarget, if found, return the subscript.

2. Hash table optimization (Optimal Solution)

  • Time complexity: O(n)
  • Space complexity: O(n)
  • Ideas：
    • Use hash tables (e.g.unordered_map)storage{value: index}。
    • Iterate over the array, for each elementnums[i],calculatecomplement = target - nums[i]。
    • examinecomplementWhether it is in the hash table:
      • If it exists, return directly{map[complement], i}。
      • Otherwise, the currentnums[i]Save to hash table.

Code implementation

Violent Enumeration (C++)

class Solution {
 public:
     vector<int> twoSum(vector<int>& nums, int target) {
         // Violent enumeration
         for(int i = 0; i < (); i++){
             for(int j = i + 1; j < (); j++){
                 if(nums[i] + nums[j] == target){
                     return {i, j};
                 }
             }
         }
         return {}; // Theoretically, the problem is guaranteed to have a solution, but it is best to add the default return value
     }
 };

Hash table optimization (C++)

Summarize

method Time complexity Space complexity Applicable
Violence enumeration O(n²) O(1) Small data volume
Hash table optimization O(n) O(n) Large amount of data

Recommended hash table optimization solution, because it significantly reduces time complexity and is suitable for larger input scales.

<Previous Next>