c++算法练习

anzhenjiang 发表于 2019-7-25 08:27

本帖最后由 anzhenjiang 于 2019-7-25 09:01 编辑

链接：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 + num = 0 ，则将这三个下标记录，l++，r--
如果num + num + num < 0 l++
如果num + num + num > 0 r--
如果碰到一定不满足或者重复的情况，记得一定要跳过这些结果。

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 > 0) break;
         if(i > 0 && nums == nums) continue;
         int l = i + 1;
         int r = nums.size() - 1;
         while(l < r){
            if(nums + nums + nums == 0) {
               res.push_back(vector<int>{nums,nums,nums});
               l += 1;
               r -= 1;
               while(l < r && nums == nums) l += 1;
               while(l < r && nums == nums) r -= 1;
            }
            if(nums + nums + nums < 0) {
               l += 1;
               while(l < r && nums == nums) l += 1;
            }
            if(nums + nums + nums > 0) {
               r -= 1;
               while(l < r && nums == nums) r -= 1;
            }
   }
}
return res; }
希望站长大人可以在发帖的时候支持一下markDown语法

苏紫方璇 发表于 2019-7-25 09:55

论坛发帖是支持makedown的

zjhd1418 发表于 2019-7-25 11:11

学习了，好东西

17791537478 发表于 2019-7-25 11:47

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

anzhenjiang 发表于 2019-7-25 13:34

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

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

anzhenjiang 发表于 2019-7-25 13:36

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

多谢夸奖:lol

anzhenjiang 发表于 2019-7-25 13:37

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

大家一起来玩啊:lol

页: [1]

吾爱破解 - 52pojie.cn's Archiver

c++算法练习