15. 3Sum

作者: jecyhw | 来源:发表于2019-05-17 10:54 被阅读0次

    题目链接

    https://leetcode.com/problems/3sum/

    解题思路

    题目要使得a + b + c = 0,且不重复,那就可以按照 a <= b <= c来满足题意,所以需要对数组从小到大排序,这样就可以先确定a,在a的右边找b和c即可,使得b + c = -a。

    代码

    class Solution {
    
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> ans;
    
            int len = nums.size() - 1;
            if (len < 2) {
                return ans;
            }
            sort(nums.begin(), nums.end());
    
            //数全部小于0
            if (nums[len] < 0) {
                return ans;
            }
    
            for (int i = 0; i < len - 1; ++i) {
                //这里nums[i]就是a,a大于,则b和c肯定都大于0,也就不用再找了
                if (nums[i] > 0) {
                    break;
                }
                if (i > 0 && nums[i] == nums[i - 1]) {//a和前一个数相等,也不再找
                    continue;
                }
    
                
                //最右边的两个数加起来也没-a大
                if (nums[len] + nums[len - 1] < -nums[i]) {
                    continue;
                }
                
                int st = i + 1, ed = len, t = -nums[i];
                while (st < ed) {
                    //nums[st]就是b,nums[ed]就是c。
                    int add = nums[st] + nums[ed];
                    if (add == t) {
                        ans.push_back({ nums[i], nums[st], nums[ed] });
                        st++;
                        ed--;
                        while (st < ed && nums[st] == nums[st - 1]) {//过滤掉重复的数
                            st++;
                        }
                        while (st < ed && nums[ed] == nums[ed + 1]) {//过滤掉重复的数
                            ed--;
                        }
                    } else if (add < t) {//b+c<-a,b往后移
                        st++;
                    } else {//b+c>-a,c往前移
                        ed--;
                    }
                }
            }
    
            return ans;
        }
    };
    
    

    相关文章

      网友评论

          本文标题:15. 3Sum

          本文链接:https://www.haomeiwen.com/subject/jidnaqtx.html