元素删除
一、删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致 。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
-
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
-
返回 k
示例1:
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例2:
输入：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 。不需要考虑数组中超出新长度后面的元素。
1.1 通过双指针
思路: 原地删除一个已排序数组中的重复元素，并返回新数组的长度，同时保证新数组中前部分的元素都是唯一的。已排序数组的特点, 由于数组是已排序的，重复的元素必定相邻。所以只需比较相邻的两个元素就能判断是否重复。双指针技巧: 使用两个指针 fast 和 slow 分别负责遍历数组和构建新数组。
-
fast指针用于扫描整个数组。 -
slow指针指向最终构建的无重复数组的下一个插入位置。
一、初始化指针: 快慢指针都从索引 1 开始。因为第一个元素（索引 0）必定是唯一的，作为无重复数组的起始部分。
二、遍历数组:
-
遍历条件: 当
fast指针还没有到达数组末尾时，持续循环。 -
比较判断: 检查当前
nums[fast]与前一个元素nums[fast - 1]是否不同-
如果不同，说明当前元素是新的、不重复的值，将其赋值到
nums[slow]位置，并将slow指针向右移动一位。 -
如果相同，则说明当前元素是重复的，直接跳过，不改变
slow的位置。 -
最后，无论是否替换，
fast指针都向右移动，继续检查下一个元素。
-
三、返回结果: 循环结束后，slow 的值表示新数组的长度（即不包含重复元素的部分）。
function removeDuplicates(nums) {
let fast = 1;
let slow = 1;
while (fast < nums.length) {
if (nums[fast] !== nums[fast - 1]) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
-
时间复杂度:
O(n)，其中n是数组的长度。快指针和慢指针最多各移动n次。 -
空间复杂度:
O(1)。只需要使用常数的额外空间。
二、删除排序数组中的重复项 II
给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例1:
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
示例2:
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。
2.1 双指针
思路: 在原地修改数组，使得每个元素最多出现两次，并返回新数组的长度。利用数组有序性, 因为数组已经排序，相同的元素是连续出现的，所以只需要检查前面两个元素就能判断当前元素是否会超过允许的两次出现。双指针技巧:
-
fast指针: 遍历整个数组，从索引2开始，检查每个元素是否可以加入结果数组中。 -
slow指针: 指向构建好结果数组的下一个插入位置，初始值为2，因为前两个元素无论如何都可以保留（最多允许出现两次）。
一、边界条件判断: 当数组长度小于或等于 2 时，无论如何每个元素都不会超过两次，直接返回原数组长度即可。
二、指针初始化: 两个指针均从索引 2 开始，因为索引 0 和 1 的元素直接保留。
三、遍历数组:
-
比较判断: 关键在于比较
nums[slow - 2]与nums[fast]-
nums[slow - 2]表示当前结果数组中，离末尾两个位置的元素。如果nums[fast]和这个元素不同，说明在结果数组中，当前值还没有出现超过两次（或者说，当前值的第一次或第二次出现），可以安全加入。 -
如果相等，说明如果加入当前的
nums[fast]就会有超过两个相同的元素（第三个重复），因此直接跳过，不将其加入结果数组。
-
-
元素加入: 当条件满足时，将
nums[fast]的值赋值给nums[slow]，然后将slow指针右移一位。 -
fast指针移动：每次循环结束都将fast指针右移一位，继续检查下一个元素。
四、返回结果: 循环结束时，slow 指针所指的位置就是新的数组长度，即有效（符合要求）元素的个数。
function removeDuplicates(nums){
if(nums.length === 2){
return 2;
}
let fast = 2;
let slow = 2;
while(fast < nums.length){
if(nums[fast] !== nums[slow - 2]){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
-
时间复杂度: ，其中
n是数组的长度。我们最多遍历该数组一次。 -
空间复杂度: 。我们只需要常数的空间存储若干变量。
三、移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
-
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要
-
返回 k
示例1:
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例2:
输入：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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
3.1 通过双指针
思路: 利用双指针（左右指针）的方法在原地移除数组中所有值为 val 的元素，同时返回移除后的新长度。
一、变量初始化:
-
left: 初始值为0，从数组起始位置开始遍历。 -
right: 初始值为nums.length，代表当前有效区域的 右边界, 即数组中还未处理的部分长度。
二、遍历过程:
-
循环条件: 当
left < right时，表示还有未处理的元素。 -
检查当前元素:
-
如果
nums[left] === val: 表示当前元素需要被移除。此时将nums[left]用当前有效区域最后一个元素nums[right - 1]覆盖。覆盖后，将right减1，因为有效区域减少了一个元素。注意，这里没有移动left，因为替换过来的新值可能也是需要移除的值，需要再次检查。 -
如果
nums[left] !== val: 当前元素不需要移除，直接将left向右移动1，继续检查下一个元素。
-
三、最终结果: 循环结束时，left 的值即为新数组的长度，数组前 left 个位置中存放的是所有不等于 val 的元素。需要注意的是，这个方法不保证原始顺序的稳定性，因为当发现要移除的元素时，会用数组末尾的元素替换它。
function removeElement(nums, val){
let left = 0;
let right = nums.length;
while(left < right){
if(nums[left] === val){
nums[left] = nums[right - 1];
right--;
}else{
left++;
}
}
return left;
}
-
时间复杂度: , 其中
n为序列的长度。我们只需要遍历该序列至多一次。 -
空间复杂度: , 我们只需要常数的空间保存若干变量。