C++ 两数之和算法优化：解决常见错误及代码改进

C++ 两数之和算法优化：解决常见错误及代码改进

本文分析了 C++ 两数之和算法中常见的错误，并提供优化后的代码解决方案，包括缩小搜索范围、处理边界情况、返回下标等改进。

原始代码：

class Solution {
public:
    void dfs(vector<int>& ans,vector<int>& nums,int l,int r,int target){
        if(l>=r) return;
        while(l<r&&l+r<=target){
            if(nums[l]+nums[r]==target){
                ans[0]=nums[l],ans[1]=nums[r];
                return;
            }
            else l++;
        }
        dfs(ans,nums,l,r-1,target);
    }
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        int r=0;
        vector<int> ans(2);
        for(int i=0;i<n;i++){
            if(nums[i]>target){
                r=i-1;
                break;
            }
        }
        if(r==0) r=n-1;
        cout<<r;
        int l=0;
        dfs(ans,nums,l,r,target);
        cout<<l<<r;
        return ans;
    }
};

问题分析：

1. 如果数组中没有小于等于 target 的数，r 可能会等于 0，导致 dfs 函数不能正确执行。
2. 在 dfs 中，应该先缩小搜索范围再进行判断，否则会出现错误结果。
3. 代码中没有对题目中要求的返回下标进行处理，需要对结果进行下标处理。
4. 代码中有一些无用的输出，需要删除。

优化后的代码：

class Solution {
public:
    void dfs(vector<int>& ans,vector<int>& nums,int l,int r,int target){
        if(l>=r) return;
        // 先缩小搜索范围再进行判断
        if(nums[l] + nums[r] > target) {
            dfs(ans, nums, l, r-1, target);
        } else if (nums[l] + nums[r] < target) {
            dfs(ans, nums, l+1, r, target);
        } else {
            ans[0] = l;
            ans[1] = r;
            return;
        }
    }
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        int r=n-1;
        // 处理边界情况
        if(nums[r] <= target) {
            int l = 0;
            vector<int> ans(2);
            dfs(ans, nums, l, r, target);
            return ans;
        } else {
            return {-1, -1}; // 数组中没有符合条件的两个数，返回 {-1, -1}
        }
    }
};

改进说明：

1. 在 dfs 函数中，先缩小搜索范围再进行判断，避免了错误结果的出现。
2. 在 twoSum 函数中，对数组中没有符合条件的两个数的情况进行了处理，返回 {-1, -1}。
3. 删除了无用的输出语句。
4. 对返回结果进行了下标处理，符合题目要求。

总结：

本文分析了 C++ 两数之和算法中常见的错误，并提供了优化后的代码解决方案，希望对大家有所帮助。在编写代码时，需要注意边界情况、缩小搜索范围等细节，才能避免出现错误结果。