秋招算法复习——515——三数之和

admin2024-05-15  0

文章目录

        • 问题描述
        • 思路分析
        • 实现代码
        • 分析与总结
问题描述

秋招算法复习——515——三数之和,在这里插入图片描述,第1张

思路分析
  • 三个之和为零,即a + b + c = 0 ,将这个拆解为b + c = -a ,那就变成了两数之和问题。两重指针的模版来解决。

秋招算法复习——515——三数之和,在这里插入图片描述,第2张

  • 虽然列表中存在重复的数字,但是结果不允许存在重复的组合,而且因为转换为两数相加问题,所以需要对数据进行排序。具体代码如下
实现代码
class Solution {
public:
    vector <vector<int>> threeSum(vector<int> &nums) {
        vector<vector<int>> res ;
        int n = nums.size();
        sort(nums.begin(),nums.end());
        for (int a = 0; a < nums.size(); ++a) {
            int tar = - a;
            int c = nums.size() - 1;
            if (a > 0 && nums[a] == nums[a - 1])  continue;
            for(int b = a + 1;b < nums.size();b ++){
                if(b > a +1 && nums[b] == nums[b - 1]) continue;

                // 开始遍历第三个元素
                while(b < c && nums[b] + nums[c] > tar) c-- ;
                if(b == c) break;
                if(nums[b] + nums[c] == tar ){
                    res.push_back({nums[a],nums[b],nums[c]});
                }
            }
        }
        return res;
    }

}
分析与总结
  • 这里还是太久没看了,就是依稀记得,写的代码结构差不多,但是具体细节记不得了。还是得多练练。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!