[数据结构与算法]1.两数之和

两数之和(C++)

题目介绍

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

核心工具

• 使用STL中find() 和 distance()

解题思路

1. 使用目标值target减去数组vector中的首个元素
2. 判断其差值是否存在，并且不等于该元素(题目要求同一个元素不能重复出现)
3. 对于vector中的元素依次进行该操作

解题源码

// 2021.07.13
using namespace std;

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

        // 进行排序，方便使用binary_search()算法
        // sort(nums.begin(), nums.end());	error

        vector<int>::iterator first = nums.begin();
        
        // 记录下标
        int i = -1;
        int j = -1;

        for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++)
        {
            // 记录target与当前元素的差值
            int cha = target - (*it);

            // 如果差值存在用cha_weizhi保存其位置
            vector<int>::iterator cha_weizhi = find(nums.begin(), nums.end(), cha);

            // 判断差值是否存在
            if (cha_weizhi != nums.end() && cha_weizhi != it)
            {
                // 使用distance算法返回下标
                i = distance(first, it);
                j = distance(first, cha_weizhi);
                
                return {i, j};
            }

        }

      return {};
        

    }
};

/*
* 注：
*   distance():
*   语法：
*   template<class InputIterator>
*   typename iterator_traits<InputIterator>::difference_type distance (InputIterator first,InputIterator last);
*   该函数会返回[first, last)范围内包含的元素的个数。
*/

出现错误

排序操作引发错误

为使用binary_find()算法提高查找速度，需要对序列进行排序
错误：vector排序后元素位置发生变化，返回下标时返回的是排序后的下标

条件判断错误

 if (cha_weizhi != nums.end() && cha_weizhi != it)
 在该语句的条件判断时缺少cha_weizhi != it 
使得题目中“数组中同一个元素在答案里不能重复出现”要求未达到