c++算法练习

anzhenjiang

链接：https://leetcode-cn.com/problems/3sum/
给定一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[  [-1, 0, 1],  [-1, -1, 2]]
一开始我以为这道题是深搜，发现我无论如何搜索，提交的结果都是超时的，后来发现这道题是一道双指针搜索数组的题，只要确定了任意一个数字，然后定义一个左指针和右指针向中间搜索。
首先需要进行排序，然后确定唯一数字和左右指针
-4 -1 -1 0 1 2
i     l             r
这里有一个数学公式 如果num + num[l] + num[r] = 0 ，则将这三个下标记录，l++，r--
如果num + num[l] + num[r] < 0 l++
如果num + num[l] + num[r] > 0 r--
如果碰到一定不满足或者重复的情况，记得一定要跳过这些结果。   

[C++] 纯文本查看 复制代码

vector<vector<int>> threeSum(vector<int>& nums) {        
    vector<vector<int>> res;        
    if(nums.size() < 3) return res;        
    sort(nums.begin(),nums.end());          
    for(int i = 0 ; i < nums.size() - 2; i ++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int l = i + 1;
            int r = nums.size() - 1;
            while(l < r){
                if(nums[i] + nums[l] + nums[r] == 0) { 
                   res.push_back(vector<int>{nums[i],nums[l],nums[r]}); 
                   l += 1;
                   r -= 1;
                   while(l < r && nums[l] == nums[l - 1]) l += 1;
                   while(l < r && nums[r] == nums[r + 1]) r -= 1;
                }
                if(nums[i] + nums[l] + nums[r] < 0) {
                    l += 1; 
                   while(l < r && nums[l] == nums[l - 1]) l += 1;
                }
                if(nums[i] + nums[l] + nums[r] > 0) {
                    r -= 1;
                    while(l < r && nums[r] == nums[r + 1]) r -= 1;
                }            
        }
    }
    return res;    }

希望站长大人可以在发帖的时候支持一下markDown语法

苏紫方璇

论坛发帖是支持makedown的

zjhd1418

学习了，好东西

17791537478

可以，代码简单精简易懂，学习了

anzhenjiang

苏紫方璇 发表于 2019-7-25 09:55
论坛发帖是支持makedown的

哈哈，我一开始写的markdown，后来发现格式乱了，还以为不支持

anzhenjiang

zjhd1418 发表于 2019-7-25 11:11
学习了，好东西

多谢夸奖

anzhenjiang

17791537478 发表于 2019-7-25 11:47
可以，代码简单精简易懂，学习了

大家一起来玩啊