15.三数之和

算法 LeetCode 双指针

字数统计: 1.1k阅读时长: 4 min

 2022/07/24 

算法：双指针+排序

两遍哈希 ⇒ O(n^2)

class Solution {
public:
    //试试hash能不能做
    vector<vector<int>> threeSum(vector<int>& nums) {
        map<int, int> a;
        vector<vector<int>> b;
        for(int i=0; i<nums.size(); i++)
            a.insert(map<int, int>::value_type(nums[i], i));
        for(int i=0; i<nums.size()-1; i++){
            for(int j=i+1; j<nums.size(); j++){
                if(a.count(0-nums[i]-nums[j])>0 && (a[-nums[i]-nums[j]]!=i) && (a[-nums[i]-nums[j]]!=j)){
                    vector<int> c(3, -1);
                    c[0] = nums[i];
                    c[1] = nums[j];
                    c[2] = 0-nums[i]-nums[j];
                    std::sort(c.begin(), c.end());
                    b.push_back(c);
                }
            }
        }
        std::sort(b.begin(), b.end());
        vector<vector<int>>::iterator iter = unique(b.begin(),b.end());
        b.erase(iter,b.end());
        return b;
    }
};

‼️问题：时间超了

双指针+排序

题目中要求找到所有「不重复」且和为 0的三元组，这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下，数组中的元素全部为 0。任意一个三元组的和都为 0。如果我们直接使用三重循环枚举三元组，会得到 O(N^3)个满足题目要求的三元组（其中 N 是数组的长度）时间复杂度至少为 O(N^3)。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高，因此我们要换一种思路来考虑这个问题。

不重复的本质：

第二重循环枚举到的元素不小于第一重循环枚举到的元素。
第三重循环枚举到的元素不小于第二重循环枚举到的元素。

所以我们要做的事情是对原有的数组进行排列，且由于对于每一重循环相邻枚举的元素相等也会造成重复（比如对于i第一次枚举到0，i+1后枚举的还是0就和上一次一样了）

而若固定了前两重循环a、b，第三重循环就应该有唯一的数c与它们对应构成解。当第二重循环往后枚举一个元素b’且b’>b，对于第三重循环就一定有c’<c。即c’一定出现在c左侧。所以我们可以从小到大枚举b，从大到小枚举c，即第二重循环和第三重循环实际上是并列的关系。

所以可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针。

这就是双指针，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2)减少至 O(N)。为什么是 O(N)呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的b），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)。还有第一重循环，时间复杂度为O(N)，因此枚举的总时间复杂度为O(N^2)。

//排序+双指针
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> b;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i=0; i<n; i++){
            //1-如果和上一次枚举的相同
            if(i>0 && nums[i]==nums[i-1])
                continue;
            //1-和上一次枚举的不相同
            int k = n-1;    //second pointer: right to left
            int target = -nums[i];
            for(int j=i+1; j<n; j++){
                //2-如果和上一次枚举的相同
                if(j>i+1 && nums[j]==nums[j-1])
                    continue;
                //2-和上一次枚举的不相同
                while(j<k && nums[j]+nums[k]>target)
                    k--;
                if(j==k)    break;
                if(nums[j]+nums[k]==target)
                    b.push_back({nums[i], nums[j], nums[k]});
            }
        }
        return b;
    }
};

Next Post

142.环形链表Ⅱ
Previous Post

预训练语言模型

CATALOG

1. 算法：双指针+排序
1. 1.1. 两遍哈希 ⇒ O(n^2)
2. 1.2. 双指针+排序