C++中用std::find在迭代器区间搜索的3Sum代码问题排查

你编写的代码如下：

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<int>::const_iterator low_it = nums.begin();
    vector<int>::const_iterator high_it = nums.end()-1;
    vector<vector<int>> ret;

    sort(nums.begin(), nums.end());
    while (low_it < high_it) {
        vector<int>::const_iterator find_it = find(low_it+1, high_it, -(*low_it + *high_it));
        if ((find_it != nums.end())) {
            ret.emplace_back(vector<int>{*low_it, *high_it, *find_it});
            low_it += 1;
            high_it += -1;
        } else if ((*low_it + *high_it) > 0)
            high_it += -1;
        else
            low_it += 1;
    }

    return ret;
}

1. std::find结果判断逻辑错误 #

你调用find(low_it+1, high_it, ...)时，查找范围是左闭右开的[low_it+1, high_it)，如果未找到目标元素，find会返回high_it而非nums.end()。但代码中用find_it != nums.end()作为判断条件，会导致：

• 未找到目标时，find_it等于high_it，而high_it不等于nums.end()，错误执行三元组添加逻辑，生成和不为0的无效结果。
• 正确判断条件应为find_it != high_it。

2. 未处理重复元素，生成重复三元组 #

当数组存在重复元素时，代码会生成完全相同的三元组。例如输入[-1,-1,0,1]，排序后两次循环都会找到0，最终返回两个[-1,1,0]。
同时，找到元素后直接移动指针，未跳过重复的low_it、high_it指向的元素，会导致重复计算。

3. 迭代器初始化顺序颠倒 #

代码先初始化low_it和high_it，再对数组排序。虽然std::sort是原地排序，迭代器不会失效，但逻辑顺序错误：排序会改变数组元素位置，先初始化迭代器再排序容易造成逻辑误解，不符合常规解题流程。正确顺序应为先排序，再初始化指针。

4. 遗漏部分有效三元组 #

找到一个符合条件的元素后，直接同时移动low_it和high_it，会跳过其他可能的有效组合。例如输入[-2,-1,0,1,2]，当low_it指向-2、high_it指向2时找到0，之后指针同时移动，会错过-2与其他元素组成的有效三元组。

修正思路参考 #

• 先对数组排序，再初始化左右指针；
• 找到目标元素后，检查并跳过重复的low_it、high_it和find_it对应的元素；
• 将find的结果判断条件改为find_it != high_it；
• 可以用双指针法替代std::find，逻辑更清晰且效率一致。

内容的提问来源于stack exchange，提问作者roeegg