Datawhale & 阿里云天池LeetCode基础训练营 c++ Code

**题意：**给一个有序的数组，其中有若干数是重复出现的，如 [1,1,2,2,2,4,] 删除重复项后为 [1,2,4]。

现要求你将重复项删除，并返回新的数组长度。

示例 1：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

STL 做法

class Solution {
public:
    int removeDuplicates(vector& nums) {
        auto last = unique(nums.begin(),nums.end());
        nums.erase(last,nums.end());
        return nums.size();
    }
};

我们每次将重复的个数统计起来，然后前移cnt个位置，就能保证前面的值都是唯一的了

class Solution {
public:
    int removeDuplicates(vector& nums) {
        int len = nums.size(), cnt = 0;
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] == nums[i-1]){
                cnt++;
                len--;
            }else{
                nums[i-cnt] = nums[i];
            }
        }
        return len;
    }
};

**题意：**给你一个数组和值val，从数组中移除所有等于val的元素

示例 1：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

和上题一样的思路，这里不再赘述

class Solution {
public:
    int removeElement(vector& nums, int val) {
        int len = nums.size();
         int cnt = 0;
         for(int i = 0; i < nums.size(); i++){
             if(val == nums[i]){
                 len--;
                 cnt++;
                 continue;
             }
             nums[i-cnt] = nums[i];
         }
         return len;
    }
};

**题意：**给定一数组，按任意顺序返回三数之和为0 的三元组，其中元素各不重复，且返回的三元组也不重复

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

这道题的难点即在于三元组判重，通过观察可发现，若要三元组不重复，其实就是使三元组的前两个元素不重复出现，

熟悉STL的朋友可以使用set> 来判重，然后第三个元素我们通过二分来查找即可

不过Set判重的复杂度也不低，可以优化一下做法:

考虑到我们将数组排序后，元素皆有序，那么问题就变成了有序数组中寻找所有不重复的二元组问题

显然，二元组的第一个元素不枚举重复的，（否则必然导致重复答案）第二个元素也是（同理）。

我实在是想不通为什么我的二分比他们枚举还慢这么多，如果有知道的大佬劳请指点一二

STL做法

class Solution {
public:
    vector> threeSum(vector& nums) {
        int n = nums.size();
        if(n < 3) return {};
        sort(nums.begin(),nums.end());
        set> st;
        vector> ans;
        
        for(int i = 0; i < n; i++){
            if(nums[i] > 0) break;
            for(int j = i+1; j < n; j++){
                int l = j + 1, r = n - 1;
                while(l < r){
                    int mid = (l+r)/2;
                    if(nums[i] + nums[j] + nums[mid] == 0){
                        l = mid;
                        break;
                    }
                    else if(nums[i] + nums[j] + nums[mid] > 0) r = mid-1;
                    else l = mid+1;
                }
                if(l < n && nums[i] + nums[j] + nums[l] == 0){
                    if(st.find(make_pair(nums[i],nums[j])) == st.end()){
                        ans.push_back(vector{nums[i],nums[j],nums[l]});
                        st.insert(make_pair(nums[i],nums[j]));
                    }
                }
            }
        }
        return ans;
    }
};

优化版：

class Solution {
public:
    vector> threeSum(vector& nums) {
        int n = nums.size(); 
        if(n < 3) return {};
        sort(nums.begin(),nums.end());
        vector> ans;
        for(int i = 0; i < n; i++){
            if(i > 0 && nums[i] == nums[i-1]) continue;//第一个位置判重
            for(int j = i+1; j < n; j++){
                if(j > i+1 && nums[j] == nums[j-1]) continue;//第二个位置判重
                int l = j+1, r = n-1;
                while(l < r){
                    int mid = (l+r)/2;
                    if(nums[i] + nums[j] + nums[mid] == 0){
                        l = mid;
                        break;
                    }
                    else if(nums[i] + nums[j] + nums[mid] > 0) r = mid-1;
                    else l = mid+1;
                }
                if(l < n && nums[i] + nums[j] + nums[l] == 0){
                    ans.push_back(vector{nums[i],nums[j],nums[l]});
                }
            }
        }
        return ans;
    }
};