Leetcode题目链接：1. 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

题目示例

示例一

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例二

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例三

输入：nums = [3,3], target = 6
输出：[0,1]

提示

2 <= nums.length <= 104
-10的9次 <= nums[i] <= 10的9次
-10的9次 <= target <= 10的9次
只会存在一个有效答案

解题思路

哈希表（map形式）

• 使用vector<int>定义数组result，用于存放最终的元素下标结果

• 使用unordered_map容器定义映射map，其中key为数组元素的值，value为数组元素对应的下标，该map映射用于存放数组中已遍历元素的信息

• for循环遍历数组nums，每遍历到一个元素，计算何值能与当前元素相加等于target值，即int num = target - nums[i]，在map中寻找num是否存在（先前是否已经在数组中找到该元素），若存在则将当前位置元素的下标和map中key为num的value值一起存入结果数组result中

• 将结果数组result作为返回值返回

暴力穷举

• 使用vector<int>定义数组result，用于存放最终的元素下标结果

• 两层for循环穷尽所有可能的结果，在循环的过程中使用continue关键词过滤相同下标的情况

• 若外层循环元素nums[i]和内层循环元素nums[j]相加等于target，则将下标 i 和 j 存入结果数组result并直接返回

• 最后将结果数组result返回

我的答案

//使用map容器
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        vector<int> result;
        for(int i = 0; i < nums.size(); i++) {
            int num = target - nums[i];
            if(map.find(num) != map.end()) {
                result.push_back(map[num]);
                result.push_back(i);
            }else {
                map.insert({nums[i], i});
            }
        }
        return result;
    }
};

//使用暴力穷举
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        for(int i = 0; i < nums.size(); i++){
            for(int j = 0; j < nums.size(); j++){
                if(i == j)continue;
                if(nums[i] + nums[j] == target){
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        }
        return result;
    }
};

提交结果