当前位置:网站首页>LeetCode-15:三数之和

LeetCode-15:三数之和

2020-11-08 23:46:21 Fool_one

题解:

  该题也可采用双指针算法,但是有三个数啊?

       这就是这一题考察的核心点所在,先枚举第一个点,另外两个点采用双指针算法,首先排序,然后去重,针对枚举第一个点,如果出现重复只取第一遍即可,后面重复元素可以直接 pass 掉

       对另外两个点,如果出现重复,可以与第一个点的做法相同,相同元素直接 pass 掉。

       采用双指针算法是可以有效降低一个 $O(n)$ 的时间复杂度的,该题的时间复杂度为 $O(n^2)$。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 三元组
        vector <vector<int>> a;
        int target;
        sort(nums.begin(), nums.end());
        // 先定一个点target,再用双指针进行扫描
        for (int i = 0; i < nums.size(); ++i) {
            // 去重操作
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if ((target = nums[i]) > 0) {
                break;
            }
            // 双指针扫描另外两个点
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                if (target + nums[l] + nums[r] < 0) ++l;
                else if (target + nums[l] + nums[r] > 0) --r;
                else {
                    a.push_back({target, nums[l], nums[r]});
                    ++l;
                    --r;
                    // 去重操作
                    while (l < r && nums[l - 1] == nums[l]) ++l;
                    while (l < r && nums[r + 1] == nums[r]) --r;
                }
            }
        }
        return a;
    }
};

       其四数之和做法是相同的,只需多一个循环即可,在此就不为大家展示了。

版权声明
本文为[Fool_one]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/xuwenchao/p/13945998.html