1.Two Sum

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 448 | 阅读时间 ≈ 2

题目描述

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

我的解法

解题思路

题目的意思是给到一个整形的数组和一个目标，要在这个数组里面找到两个数相加等于这个目标的两个数，并返回这两个数的索引数组。并且可以假定每个输入必有且只有一个解，不能用一个数两次。

简单的想法就是用两个for循环，遍历数组里两个数相加的组合，如果相加等于目标，就返回这两个索引值。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> index;
        for (int i = 0; i < nums.size() - 1;i++){
            for (int j = i + 1; j < nums.size(); j++){
                if (nums[i] + nums[j] == target){
                    index.push_back(i);
                    index.push_back(j);
                    return index;
                }
            }
        }
        return index;
    }
};

结果如下：
✔ Accepted
✔ 29/29 cases passed (144 ms)
✔ Your runtime beats 32.13 % of cpp submissions
✔ Your memory usage beats 99.9 % of cpp submissions (9.2 MB)
速度有点点的慢

高票解法

看了下高票以及速度较快的解法，基本都是用了hash表。之前做题的时候也经常可以见到，但是一直也都没有太理解它的用法

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> indices;
        for (int i = 0; i < nums.size(); i++) {
            if (indices.find(target - nums[i]) != indices.end()) {
                return {indices[target - nums[i]], i};
            }
            indices[nums[i]] = i;
        }
        return {};
    }
};

知识总结

先好好了解一下哈希表和C++中的map和inorder_map的用法。