2022-02-14Leetcode训练营

天池训练营链接三数之和

暴力3层循环+去重1双指针 移除元素删除有序数组中的重复项

天池leetcode训练营

链接
摘自题解：
「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：
第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说，我们枚举的三元组（a,b,c) 满足 a<=b<=c，保证了只有 (a,b,c)这个顺序会被枚举到，而(b,a,c) 、(c,b,a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。

同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。

这段代码，3重循环全都从前往后，结果是超时，逻辑错

class Solution {
    //暴力3层循环+去重
public:
    vector> threeSum(vector& nums) {
        sort(nums.begin(), nums.end());
        //注意排序
        vector> res;
        if(nums.size() < 3){
            return res;
        }
        for(int i=0;ii+1 && nums[j] == nums[j-1]){
                    //++j;
                    continue;
                }
                for(int k=j+1; kj+1 && nums[k] == nums[k-1]){
                        //++k;
                        continue;
                    }
                    if(nums[i]+nums[j]+nums[k] == 0){
                        //vector temp;
                        //temp.push_back(nums[i]);
                        //temp.push_back(nums[j]);
                        //temp.push_back(nums[k]);
                        res.push_back({nums[i],nums[j],nums[k]});
                        //可以直接组好push进去
                    }
                    //建vec并push 3个
                   // vec push进res
                }
            }
        }
        return res;
    }
};

换命名，first，second，third，三数和在第二层循环开始转化为两数和来处理，后面就是模板
时间复杂度O(n^2)

class Solution {
    //暴力3层循环+去重
public:
    vector> threeSum(vector& nums) {
        sort(nums.begin(), nums.end());
        //注意排序
        vector> res;
        if(nums.size() < 3){
            return res;
        }
        int n=nums.size();
        for(int first=0;firstfirst+1 && nums[second] == nums[second-1]){
                    //注意j>i+1这里，二层循环不能重复，但j=i+1可以和前面一样
                    //++j;
                    continue;
                }
                while(second < third && nums[second] + nums[third] > target){
                    --third;
                }
                if(second == third){
                    break;
                }
                if(nums[second]+nums[third] == target){
                        //vector temp;
                        //temp.push_back(nums[i]);
                        //temp.push_back(nums[j]);
                        //temp.push_back(nums[k]);
                    res.push_back({nums[first],nums[second],nums[third]});
                        //可以直接组好push进去
                }
                    //建vec并push 3个
                   // vec push进res
                
            }
        }
        return res;
    }
};

链接
感触就是数组原地处理的题直接双指针，和链表差不多处理方式

class Solution {
public:
    int removeElement(vector& nums, int val) {
        int n = nums.size();
        if(n == 0){
            return 0;
        }
        int left = 0;
        for(int i=0; i 
删除有序数组中的重复项 
链接
 仍然双指针，和上一题差不多
 
class Solution {
public:
    int removeDuplicates(vector& nums) {
        //排序
        sort(nums.begin(), nums.end());
        //这句，有序数组不需要..
        int n = nums.size();
        int cur = 0;//当前指针
        if(n==0) return 0;
        if(n==1) return 1;
        for(int i=1; i