LeetCode刷算法题 - 1. Two Sum

数据结构与算法的重要性就不多说了，几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的，程序猿们都懂的，现在最权威流行的刷题平台就是 LeetCode。闲话少讲，步入正题。

LeetCode原题链接

C++ vector 容器浅析

C++ Map常见用法说明

Question(Easy):

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].

Talk is cheaper, show code.

Solution

以下代码皆是本人用 C++写的，觉得还不错的话别忘了点个赞哦。各位同学们如果有其他更高效解题思路还请不吝赐教，多多学习。

A1、双重循环

算法时间复杂度 O(n^2)，Runtime: 212 ms，代码如下

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){
        
        vector<int>obj;
        
        for (int i=0; i<nums.size()-1; i++)
        {
            for (int j=i+1; j<nums.size(); j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    obj.push_back(i);
                    obj.push_back(j);
                    return obj;
                }
            }
        }
        return obj;
    }
};

A2、HashMap一层循环

将给定数组的值作为Map的Key，值对应索引位置为Value。通过一次循环查询target值减去当前Map指向的值所得到的值是否在Map中即可，如果存在则直接返回该元素和当前Map指向元素的位置。
算法的时间复杂度为O(n)，Runtime: 10 ms，代码如下:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){
        
        vector<int>obj;
        map<int,int> map;
        
        //  为HashMap赋值，重复值只会取最后一次出现的，重复值无用
        for (int i=0; i<nums.size(); i++)
        {
            map[nums[i]] = i;
        }
       
        // 开始遍历查询
        for (int i=0; i<nums.size(); i++)
        {
            // 得到与当前值的匹配值
            int search = target - nums[i];
            
            // 查询匹配值是否存在于HashMap中，并且匹配值不能是自己
            if (map.find(search) != map.end() && map[search] != i)
            {
                obj.push_back(i);
                obj.push_back(map[search]);
                
                return obj;
            }
        }
        
        return obj;
    }
};

A3、优化HashMap减少一次循环

大致与A2相同，优化不再单独创建循环为HashSet赋值，而是利用每次在HashSet中查找时同时在HashSet中加入新的值，可以减少一次赋值循环，但对于所查找的两个值的位置，只有在搜索靠后的值时，整个过程才会返回结果。（因为搜索到第一个匹配值时，第二个匹配值还没有被放到HashSet中）。
算法时间复杂度同样为O(n)，Runtime: 9 ms，代码如下

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){
        
        vector<int>obj;
        map<int,int> map;
       
        // 开始遍历查询
        for (int i=0; i<nums.size(); i++){

            // 得到与当前值的匹配值
            int search = target - nums[i];
            
            // 查询匹配值是否存在于HashMap中，并且匹配值不能是自己
            if (map.find(search) != map.end() && map[search] != i){
                obj.push_back(i);
                obj.push_back(map[search]);
                return obj;
            }
            map[nums[i]] = i;
        }
        
        return obj;
    }
};

引用相关

LeetCode 官网
LeetCode 答题纸