1：两数之和（C++）

题目地址：https://leetcode-cn.com/problems/two-sum/

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

题目示例

示例:

给定 nums = [2, 7, 11, 15], target = 9 

因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

解题思路

思路1：暴力遍历寻找两数之和，时间复杂度O(n^2)，空间复杂度O(1);

思路2：双指针求解，先对数组nums排序，然后使用指针i和j分别指向数组首尾进行遍历求解，时间复杂度O(nlogn)，空间复杂度O(n)；

思路3：哈希表求解，根据数组元素的散列值组织成桶以允许通过它们的键值直接快速访问单个元素，遍历数组nums，每次查找target-nums[i]是否存在，时间复杂度O(n)，空间复杂度O(n)；

程序源码

暴力法

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

双指针

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        vector<pair<int, int>> nums1;
        for(int i = 0; i < nums.size(); i++)
        {
            nums1.push_back(make_pair(nums[i], i));
        }
        sort(nums1.begin(), nums1.end());
        int i = 0, j = nums1.size() - 1;
        while(i < j)
        {
            if(nums1[i].first + nums1[j].first == target)
             {  
                 res.push_back(nums1[i].second);
                 res.push_back(nums1[j].second);
                 break;
             }
             nums1[i].first + nums1[j].first > target ? --j: ++i;
        }
        return res;
    }
};

哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //暴力枚举：O(n^2)、O(1)
        /*vector<int> res;
        if(nums.size() < 2) return res;
        for(int i = 0; i < nums.size() - 1; i++)
        {
            for(int j = i + 1; j < nums.size(); j++)
            {
                if(nums[i] + nums[j] == target) 
                {
                    res.push_back(i);
                    res.push_back(j);
                }
            }
        }
        return res;*/
        //哈希表：O(n)、O(n)
        if(nums.size() < 2) return {};
        unordered_map<int, int> mp;
        vector<int> res;
        for(int i = 0; i < nums.size(); i++)
        {
            if(mp[target - nums[i]] != 0 && mp[target - nums[i]] != i + 1) //防止利用同一个元素
            {
                res.push_back(i);
                res.push_back(mp[target - nums[i]] - 1);
                return res;
            }
            mp[nums[i]] = i + 1; //防止处理哈希表下标为零的情况
        }
        return res;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int,int> mp;
        for(int i = 0; i < nums.size(); ++i)
        {
            mp[nums[i]] = i;
        }
        for(int i = 0; i < nums.size(); ++i)
        {
            int index = target - nums[i];
            if(mp.count(index) && mp[index] != i)
            {
                res.push_back(i);
                res.push_back(mp[index]);
                break;
            }
        }
        return res;
    }
};