1、两数之和

      题目：
               给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数， 并返回他们的数组下标。你不能重复利用这个数组中同一元素（即相同下标的元素只能用一次）。
               例如

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

给定 nums = [1,2,3,4], target =4
因为 nums[0] + nums[2] =1+3 = 4 所以返回 [0, 2]

给定 nums = [2,1,0,2,3,4], target =4
因为 nums[0] + nums[3] =2+2 = 4 所以返回 [0, 3]是可以的

你只需要找出一组符合要求的组合即可

思路：双重循环暴力查找。找到则把下标用push_back()方法添加到返回的向量（容器）中，然后直接从函数中返回

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

时间只超过了24%的提交
这是python版实现的 python版两数之和

--------------------------2020.1.9更新--------------------------
这是返回数组中N个数之和为一个常数的代码，result里面每一行就是一种组合（值的组合，不是下标组合）

class Solution {
public:

bool calNextNumber(int start, int target, int N, vector<int>&temp, vector<int>nums)
{
	if (target == 0 && N == 0)       //目标值减为0个数qieN变成0说明找到了，返回ture
		return true;
	if (start + N > nums.size() || target < 0)  //目标值减到小于0说明之后的值都不可以了（之后的值肯定比当前值要大，我们排过序），还有就是当前位置往后没有N个数了也不行，返回false
		return false;
	for (int i = start; i < nums.size(); ++i){  //这儿本来还可以加上一个判断，如果target比数组最大值大则循环到数组最后，但如果小，就循环到比target小的位置就行，但似乎没有改进太多性能，就没弄了
		temp.push_back(nums[start]);  //把开始位置的值加入本次序列里面
		if (calNextNumber(i + 1, target - nums[start], N - 1, temp, nums)){ //从数组中找n-1个数和为target是否可行
			return true;
		}
		temp.pop_back();//不可行就把当前这个开始位置的值给弹出，这儿和前面的push_back对应。然后从下一个位置继续找
	}
	return false;
}
 
vector<vector<int>> cal(vector<int> nums, int target, int N)
{
	vector<vector<int>> result;
	vector<int> temp;
	for (int start = 0; start < nums.size()-N; ++start){
		if (calNextNumber(start, target, N, temp, nums))  //从数组中找n个数和为target是否可行，找到ivec里面是N个数，我这儿传的是引用
			result.push_back(temp); //找到就加入总序列
		temp.clear();   //然后不管找没找到都把这个temp中间容器给清空。方便下一次用
	}
	return result;
}
    vector<int> twoSum(vector<int>& nums, int target) {
        int N=2;  //N可随意更改，代表查找N个数的和
        sort(nums.begin(), nums.end());
        vector<vector<int>> result = cal(nums, target, N);
        for(int i=0;i<result.size();++i){
            for(int j=0;j<N;++j){
                cout<<result[i][j]<<"   ";
            }
            cout<<endl;
        }
        return result[0];
    }
};

--------------------------2020.1.12更新--------------------------
利用双指针来做

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res,tmp1;
        int l=0, r=nums.size()-1,flag=0;
        tmp1=nums;
        sort(tmp1.begin(), tmp1.end());
        while(l!=r){
            if(tmp1[l]+tmp1[r]==target){
                flag=1;
                break;
            }
            else if(tmp1[l]+tmp1[r]<target)     l++;
            else    r--;
        }
        if(flag==1){
            for(int i=0;i<nums.size();++i){
                if(nums[i]==tmp1[l])   res.push_back(i);
                else if (nums[i]==tmp1[r])  res.push_back(i);
            }
        }
        return res;  
    }
};

--------------------------2020.1.12更新--------------------------
利用hash表来做

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> a;       //提供一对一的hash
        vector<int> b(2,-1);  //用来承载结果，初始化一个大小为2，值为-1的容器b
        for(int i=0;i<nums.size();++i){
            if(a.count(target-nums[i])>0){
                b[0]=a[target-nums[i]];
                b[1]=i;
                break;
            }
            a[nums[i]]=i;//反过来放入map中，用来获取结果下标
        }
        return b;    
    }
};

c++关于map的find函数和count函数的使用https://blog.csdn.net/qq_43657442/article/details/103943045

1、两数之和

原文：https://www.cnblogs.com/2944014083-zhiyu/p/14738708.html