[leetcode数组系列]2三数之和

[leetcode数组系列]2三数之和

前言

秋招的结束，面试了大大小小的公司，最大的问题在于算法上。所以打算坚持在leetcode打卡，看看到底能不能行，如果你想见证，那我来开车，你坐稳，一起走向更好的远方。在学习今天内容之前，先学习上一篇的两数之和会更好哟leetcode两数之和求解

一 题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

1 leetcode链接

给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[[-1, 0, 1],[-1, -1, 2]]

2 思路1---暴力解法

在思考两数之和解决方法的时候，我们使用了两层循环把所有的结果给求出来，相信读者很快就想到三数之和我就用三个循环，很棒，思路是一样，只是之前的a+b=0,现在的b=c+d了。好了代码呈上。

class Solution {public:    vector> threeSum(vector& nums) {        if(nums.size()<3) return{};        vector> res;//结果        set> ret;//用来去重        for(int i=0;i tp;                        int a=(nums[i]nums[j]?nums[i]:nums[j])>nums[k]?(nums[i]>nums[j]?nums[i]:nums[j]):nums[k];//放最大的元素                        int c=0-a-b;                        tp.push_back(a);                        tp.push_back(c);                        tp.push_back(b);                        ret.insert(tp);                    }                }            }        }        for(auto it:ret)        {            res.push_back(it);        }        return res;    }};

3 思路2---排序加双指针

下面先看看整体的代码，随后图解整个代码流程以及如何处理重复的情况

c++版本

class Solution {public:    vector> threeSum(vector& nums) {         int target;        vector> ans;        sort(nums.begin(), nums.end());        for (int i = 0; i < nums.size(); i++) {            if (i > 0 && nums[i] == nums[i - 1]) continue;            if ((target = nums[i]) > 0) break;            int left = i + 1, right = nums.size() - 1;            //取出三个数 所以不用left=right            while (left < right) {                if (nums[left] + nums[right] + target < 0) ++left;                else if (nums[left] + nums[right] + target > 0) --right;                else {                    ans.push_back({target, nums[left], nums[right]});                    ++left, --right;                    //去重                     //测试数据[-2,0,0,2,2]                    while (left < right && nums[left] == nums[left - 1]) ++left;                    while (left < right && nums[right] == nums[right + 1]) --right;                }            }        }        return ans;     }};

一次循环的图解

python版本

class Solution:    def threeSum(self, nums: List[int]) -> List[List[int]]:        nums.sort()        n = len(nums)#获取列表长度        res = []#存放结果        for i in range(n):            if i > 0 and nums[i] == nums[i-1]:                continue            num1 = nums[i]#取得定值            if num1 > 0:                break            #定义双指针初始状态            j = i + 1            k = n - 1            while j < k:                total = num1 + nums[j] + nums[k]                if total == 0:                    res.append((num1, nums[j], nums[k]))                    j += 1                    while nums[j] == nums[j-1] and j < k:                        j += 1                    k -= 1                    while nums[k] == nums[k+1] and j < k:                        k -= 1                elif total > 0:                    k -= 1                    while nums[k] == nums[k+1] and j < k:                        k -= 1                else:                    j += 1                    while nums[j] == nums[j-1] and j < k:                        j += 1        return res

4 总结

文中使用了两种方式来解决这个问题，第一种为复杂度较高的暴力解答，第二种使用了类似快排思想的双指针法，后面还会有更多关于双指针的用法，敬请期待。至此，想想有学会点什么了？

5 结尾

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。