[LeetCode]1. Two Sum

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

给定一个数组,一个数字target, 在数组中查找两个数之和等于target. 返回查找的下标.

假定每个target只有一个solution,不能重复使用元素.

Solution

Analysis

最朴素的办法: 双层循环. 时间复杂度O(N*N). 这个就不介绍了.

改进方法: O(N). 借助hash表[空间换时间]. hash表记录元素与下标对应关系. 这里我们不用事先对hash表进行初始化. 边循环数组边赋值: 如果查找元素不存在,进行赋值.

具体代码如下:

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> tabel;
        
        vector<int> result;
        
        for (int i=0; i< nums.size(); ++i){
            // 查找数字为target-nums[i]; 如果存在说明找到答案, nums[i]也不用存到hash表,直接退出循环,返回结果
            if (tabel.find(target - nums[i]) != tabel.end()){
                result.push_back(tabel[target-nums[i]]);
                result.push_back(i);
                break;
            }
            // 不存在, 存入hash表
            tabel[nums[i]] = i;
        }
        
        return result;
    }
};

Problem

Solution

Analysis

Code

推荐文章（由hexo文章推荐插件驱动）