前言

有人相爱，有人夜里开车看海，有人连leetcode第一题都做不出来。—— 摘自评论

参考

没啥参考的，用到啥函数了就回头看看。毕竟记得不是很清楚。

正文

从题目要求里看形式就像输入一个数组和一个目标数，求数组中哪两个成员能组合成这个目标数。

默认给的模板是：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

    }
};

估计是因为c++ 有stl思想，所以不用数组，而使用容器vector

初解

暴力解法我们肯定想到的是两层for循环直接挨个if过来
实现：
时间复杂度按照这样说好像就是T(n)=O(n^2);

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> n;
        for(int i=0;i<nums.size();i++){
            for(int j=1;j<nums.size();j++){
                if(nums[i]+nums[j]==target){
                    n.push_back(i);
                    n.push_back(j);
                    return n; //或者直接break结束循环，反正最后都要返回。
                }
            }
        }
        return n;
    }
};

最初的时候想创建一个数组返回的，但是题目用的好像是vector，也就凑合用了，后面看了下评论，发现return居然能返回{}，这样的一组数据，就感觉很新奇也很离谱。。毕竟传统概念return都是返回一个变量或者值

{}的解释

后面多看了几个评论，发现类似传递的规则，应该是默认将{}转换成这个函数类型相符的了，比如java的可能是public int[] twoSum，那么return的是，默认就是return int[] {i,j}.

至于为什么这么说呢，因我自己试了一下：

是可以通过测试，并且提交也是正确的，那么ok就不用管这么多了，虽然感觉在实际的面试中应该出的题目会和这个不太一样，如果有需要开辟就开辟下新的空间用吧。

调试初解

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

故此这里开始都使用{}的方法，这样雀食省了空间，但是还没搞懂为什么能这么用，看后续能不能看到

运行代码的时候发现输出和预期结果不一样：

看了一下发现j不应该也从0开始，浪费了，那么把j的初始化设置为1；

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

再次执行测试：

哎发现可以了，提交看看

哎然后，然后就报错了。。

又看了一下题目:你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
原来是不允许重复啊。那么在if里面在判断一次i！= j即可

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

提交代码：
ok通过了。。但是这个执行用时才击败了5.12%的用户也太搞了。。不得不感慨人和人之间的差距。

优化

又看了下我的代码，看看哪能优化一丢丢，想了想，在i和j那里可以做做手脚。
比如测试样例是nums=[2,5,5,11],target=10;
我i肯定是从0开始，但是j呢，从1开始是没啥问题，但是如果

第一次i=0，j就从1-end。
第二次i=1，j还是从1-end。
第三次i=2，j还是从1-end。

这样以来就能简单的看出问题所在之处了。

所以我们的j应该是=1+i，这样一来

第一次i=0，j=1+0 —— end
第二次i=1，j=1+1 —— end
第三次i=2，j=1+2 —— end

这样可以说大小省略掉一半的时间了。

简单修改一下代码：

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