26. 删除排序数组中的重复项

[Geekhyt]

原题链接

双指针

题目要求原地删除重复出现的元素，不要使用额外的数组空间，返回移除后数组的新长度。

先明确，这道题给我们提供的是排好序的数组，所以重复的元素必然相邻。

所以实际上我们只需要将不重复的元素移到数组的左侧，并返回其对应的长度即可。

1.借助双指针，i 从索引 0 开始，j 从索引 1 开始。
2.当前项 nums[j] 与前一位置 nums[j - 1] 相等时，j++ 跳过重复项。
3.当二者不相等时，意味着不是重复项，此时需要将 i 指针右移， 并将 nums[j] 复制到此时的 nums[i] 位置上，然后将指针 j 右移。
4.重复上述过程，直到循环完成，最终返回 i + 1，因为题目要求返回长度，i 是索引位置，加 1 即所求。

const removeDuplicates = function(nums) {
    const n = nums.length
    let i = 0
    if (n === 0) return 0
    for (let j = 1; j < n; j++) {
        if (nums[j] !== nums[j - 1]) {
            i++
            nums[i] = nums[j]
        }
    }
    return i + 1
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)