两数之和

1.题目内容

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1
2
3

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

示例 2：

1
2

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

示例 3：

1
2

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

提示：

• 2 <= nums.length <= 104

• -109 <= nums[i] <= 109

• -109 <= target <= 109

• 只会存在一个有效答案

2.解法

（1）哈希表

思路及算法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

//Java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1)地寻找 target - x。

• 空间复杂度：O(N)，其中 N是数组中的元素数量。主要为哈希表的开销。

（2）蛮力枚举

思路及算法

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//Java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

复杂度分析

• 时间复杂度：O(N^2^)其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

• 空间复杂度：O(1)。

习题1：

将这段话改为2级标题

习题2：

试着在你的Typora中编辑下面的内容：

这是第1行

这是第2行

这是补充内容

这是第3行

1
2
3
4

这是第一行
这是第二行
这是补充内容
这是第三行

习题3：

将下面的内容改为指定的格式要求：

==黑体== 斜体 下划线 ==高亮==

黑体加下划线，并高亮显示

拓展题：

试着输入1*2*3*...*99，如何解决*不显示的问题？

1^^2^^3^^…^^99

试着输入\*，如何解决\消失的问题？

*

习题4：

试着打出x~1~^2^，观察它的结果是不是$x_1^2$​，了解上下标的局限性。

x1^2^

int a=0;

习题5：

试着使用列表编辑出下面的效果：

1. 删除官方YUM库

2. 编写本地YUM库配置文件

   • 内容：

     一个图片。

   • 注意事项

3. 安装挂载光盘：

   1. 插入光盘并通电，挂载
   2. 将上述挂载命令写入

习题6：

1. 将习题5中的一个图片前增加区块（不是前一行）。
2. 试着打出下面的效果。

我们处在一个区块里。

对的，没错。

我们处在一个区块里。

不，不对。

习题7：

使用行内代码美化下面第一段的内容（第二段用于对照）：

即使cv::Vec<>是模板，但大部分的时间你都不会倾向于使用它的这个形式。相对的，有很多它的别名（typedef）以便用于通用的实例。它们有着cv::Vec2i, cv::Vec3i和cv::Vec4d这样的名称（分别对应于2个元素的整型向量、3个元素的整型向量和4个元素的双精度浮点向量）。任何有着cv::Vec{2,3,4,6}{b,w,s,i,f,d}形式的声明（b=unsigned char，w=unsigned short，s=short），对于2个到6个维度的6种数据类型的任何组合都是有效的。

即使cv::Vec<>是模板，但大部分的时间你都不会倾向于使用它的这个形式。相对的，有很多它的别名（typedef）以便用于通用的实例。它们有着cv::Vec2i, cv::Vec3i和cv::Vec4d这样的名称（分别对应于2个元素的整型向量、3个元素的整型向量和4个元素的双精度浮点向量）。任何有着cv::Vec{2,3,4,6}{b,w,s,i,f,d}形式的声明（b=unsigned char，w=unsigned short，s=short），对于2个到6个维度的6种数据类型的任何组合都是有效的。

习题8：

下面试图使用多行脚注，但预期效果不对，如何解决？

右边是对我^1的解释。

这是第二行。

习题9：

试着插入一个图片，要求图片缩小1/2，左对齐。

习题10：

下面有两个相邻的表格，如何在二者之间增加内容？

1

我是一段很长的代码

1

我是另一段很长的代码

###1.这是第一次尝试

记录自己第一次搭建博客。