To address a common programming problem (since the original problem statement was missing), let's solve the Two Sum problem, a classic entry-level problem.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
Assumptions: Each input has exactly one solution, and you may not use the same element twice. The answer can be in any order.

Approach

The optimal approach uses a hash map (unordered_map in C++) to achieve linear time complexity:

1. Hash Map Storage: Store each number and its index as we iterate through the array.
2. Complement Check: For each number, compute the complement (target - current number). If the complement exists in the hash map, return the indices of the complement and the current number.
3. Insert Current Number: If the complement is not found, add the current number and its index to the hash map.

This approach runs in O(n) time (average case for hash map operations) and uses O(n) space (to store the hash map).

Solution Code

#include <vector>
#include <unordered_map>

using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numIndexMap; // Key: number, Value: index

    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];

        // Check if complement exists in the map
        if (numIndexMap.find(complement) != numIndexMap.end()) {
            return {numIndexMap[complement], i};
        }

        // Insert current number and its index into the map
        numIndexMap[nums[i]] = i;
    }

    // According to problem statement, this line is unreachable (exactly one solution exists)
    return {};
}

Explanation

• Hash Map: The unordered_map allows us to quickly look up the complement of the current number (O(1) average time).
• Iteration: We loop through the array once, so the time complexity is O(n).
• Correctness: Since the problem guarantees exactly one solution, we will always find the complement before the loop ends.

Example: For nums = [2,7,11,15] and target =9, the complement of 2 is 7 (not in the map, so add 2:0). Next, the complement of 7 is 2 (found in the map at index 0), so return [0, 1].

This solution is efficient and easy to understand, making it a standard approach for the Two Sum problem. If you had a different problem in mind, feel free to share the details!

作者声明:本文包含人工智能生成内容。