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

Datawhale & 阿里云天池LeetCode基础训练营 Task1: 数组 课后习题 1、删除有序数组中的重复项（Easy）

**题意：**给一个有序的数组，其中有若干数是重复出现的，如 [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; }};

2、移除元素（Easy）

**题意：**给你一个数组和值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; }};

3、三数之和（Medium)

**题意：**给定一数组，按任意顺序返回三数之和为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; }};