题目概述
-
题号：1. 两数之和
-
难度：简单
-
内容：
1 2 3 4 5 6 7 8 9 10 11
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
第一次思路
首先能够想到的就是暴力法，即用 target减去 数组 nums 的的第一个，差temp 和 nums 依次比较，遇到相等的就是返回，这就是我们要寻找的数。不等，继续循环至查询完毕。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void sums(vector<int>& nums, int target)
{
// 置空判断
if (nums.size() < 2)
{
//return false;
}
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] <= target)
{
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[j] + nums[i] == target)
{
cout << i;
cout << j;
}
}
}
}
}
上述代码，我添加了一个 if 判断：如果 nums[i] < target 就不执行for循环，可是我忘记了负数的情况，如果 ：nums = [-1, -2, -3, -5], target = -8，那么这个 if 判断就会使得所有的 item 都不进行判断，error ！
所以，应该将 if 判断删去
测试 Submit
简直是 low 到爆的方法
分析
上述解法的本质是：**target - nums[ i ] = temp，然后查询 nums 数组剩下的元素是否有等于 temp **
那么，问题就变成了：在一个数组中查找指定元素 效率怎样才能最高？
改进
这就要引入 unordered_map，哈希表，一种查找速度极快的数据结构，元素混序且不可重复
（ map 的特点是有序性，适用于有顺序要求的问题，查找速度略慢于 unordered_map）
改进Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void hashSum(vector<int>& nums, int target)
{
// 哈希表
unordered_map<int, int> hash;
//返回vector
vector<int> res;
//填充hash
for (int i = 0; i < nums.size(); i++)
{
hash[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i++)
{
int temp = target - nums[i];
if (hash.count(temp) && hash[temp] != i) //count()方法：返回查找元素的个数（非0即1）
{
res.push_back(i);
res.push_back(hash[temp]);
cout << i << hash[temp] << endl;
break;
}
}
}
改进 Submit
收获总结
这次没有考虑到的是负数的情况，以致于进行了错误的 if 判断。考虑的还是不够全面。
因为是再一次使用 C++ 去敲，之前的一些语法忘了大部分，这里特此总结：
-
方法在使用前必须进行声明：
1 2 3 4 5 6 7
//函数声明 void sums(vector<int>&, int); void sums(vector<int>&, int) { //具体实现部分 }
-
vector用法1 2 3 4
vector<int> v; //声明 v.push_back(1); //添加元素 v.pop_back(1); //删除元素 v[0]; //取元素
-
unordered_map用法1 2 3 4
unordered_map<int, int> hash; //定义 hash[key] = value; //赋值 hash.count(temp); //查询是否存在temp这个key 结果非0即1（因为unordered_map内元素不能重复） int a = hash[temp]; //取得key=temp的对应值value
