Easy_01

两数之和

想法一：最直接的暴力解法。通过两层嵌套循环对数组进行遍历。

 vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> index;

        for(int i = 0;i < nums.size() - 1; ++i){

            int num_i = nums[i];

            for (int j = i + 1; j < nums.size();++j){

                int num_j = nums[j];

                if (num_i + num_j == target){

                    index.push_back(i);

                    index.push_back(j);

                    return index;  

                }

            }

        }

        return index;

    }

结果

简单明了直接通过，但结果并不是很好。

解法二：创建一个辅助数组用于排序。利用有序的数组做差在原来的数组寻找查找对应的下标。

 vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> index;

        vector<int> temp_nums(nums.begin(),nums.end());

sort(temp_nums.begin(),temp_nums.end()); 

for (vector<int>::iterator it = temp_nums.begin();it != temp_nums.end();++it){

    int gap = target - *it;

        vector<int>::iterator index_itr1 = find(nums.begin(),nums.end(),*it);

        int temp = *index_itr1;

        *index_itr1 = target+1; //防止重复的数据产生问题

        vector<int>::iterator index_itr2 = find(nums.begin(),nums.end(),gap);

        if (index_itr2 != nums.end()){

            int index_i = index_itr1 - nums.begin();

            int index_j = index_itr2 - nums.begin();

            index.push_back(index_i);

            index.push_back(index_j); 

            return index;

        }

       *index_itr1 = temp;

}

return index;

}

提交了2次才成功。

第一次出现的问题：数组没考虑到0

第二次出现的问题：数组没考虑到负数情况

从结果可以看出：执行时间提升，但是由于使用了辅助数组，内存的消耗仍然是一个问题