LeetCode/两数之和
给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标
思路：求两数和等于目标值，首先考虑二重循环暴力求解，分别将每一个数与所有数进行求和匹配，时间复杂度为O(n2)。进一步可以考虑两求和数一个值大于目标值一半，一个值小于一半，可以分割成两部分进行匹配。若能使用C++容器模板，考虑使用哈希表hash_map进一步降低二重循环里匹配所需时间。
1. 暴力求解
双重循环
int* twoSum(int* nums, int numsSize, int target) {
int i,j;
int *result=NULL;
for(i=0;i2. 哈希表优化
class Solution {
public:
vector twoSum(vector& nums, int target) {
map a;//提供一对一的hash
vector b(2,-1);//初始化一个大小为2，值为-1的数组，存放最终结果
for(int i=0;i0)//匹配的值存在哈希表中
{
b[0]=a[target-nums[i]];//获取匹配值的位置
b[1]=i; //存储另一值位置
break;
}
a[nums[i]]=i;//值为键来获取位置，维护扩大一个哈希表用于查询
}
return b;
};
};
3. 三数之和
先排序，即方便跳过相同的数，也便于双指针的移动，再使用双指针求两数之和
class Solution {
public:
vector> threeSum(vector& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector> ans;
// 先枚举 a ，再枚举b，这种遍历的结构注定不会重复，得到其组合数
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) //移动到不重复的位置
continue;
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];//目标和，将问题转换为两数之和
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1])//移动到不重复位置
continue;
// 需要保证 b 的指针在 c 的指针的左侧，左右指针交替移动，这里移动右指针
while (second < third && nums[second] + nums[third] > target) //和大于目标值
--third; //移动右指针
if (second == third) break;//两指针会和遍历结束，其实循环用while的话不用加这句
if (nums[second] + nums[third] == target) {//找到目标值的话存入结果
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};