关于leetcode:LeetCodeGolang-26-删除有序数组中的重复项

题目：

给你一个 升序排列 的数组 nums，请你 原地 删除反复呈现的元素，使每个元素 只呈现一次，返回删除后数组的新长度。元素的 绝对程序 应该放弃 统一。

因为在某些语言中不能扭转数组的长度，所以必须将后果放在数组 nums 的第一局部。更标准地说，如果在删除反复项之后有 k 个元素，那么 nums 的前 k 个元素应该保留最终后果。

将最终后果插入 nums 的前 k 个地位后返回 k。

不要应用额定的空间，你必须在 原地 批改输出数组 并在应用 O(1) 额定空间的条件下实现。

• 0 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 升序 排列

题解：

首先，这是一道数组类的简略算法题。咱们明确循环不变式（loop invariant）的概念，即一组在循环体内、每次迭代均放弃为真的性质。

先贴代码：（GO 语言）

func removeDuplicates(nums []int) int {n := len(nums)
   if n < 2 {return n}
   slow, fast := 1, 1
   for fast < n {if nums[fast-1] != nums[fast] {nums[slow] = nums[fast]
         slow++
      }
      fast++
   }
   return slow

咱们设置的循环不变式：slow指针之前的数组元素（不蕴含目前所指元素）不反复。同时应用快慢指针的形式。

• 初始 slow 设为 1，即nums[1] 之前的元素不反复，因为 nums[1] 之前最多有一个元素，肯定不会呈现反复，所以 slow 地位满足不变式要求。
• 接下来的循环中，如果 nums[fast] 与nums[fast-1]不雷同，因为数组升序，则将 nums[fast] 赋值给 nums[slow] 后后移 slow，完结本次循环。如果nums[fast] 与nums[fast-1]雷同，则间接完结本次循环。每次循环，slow地位均满足不变式要求。
• 最终 fast 指针遍历完数组元素后，完结整个循环，slow地位满足不变式要求。

因而在循环完结后，slow左侧元素均为不反复元素，合乎算法要求。

复杂度剖析：

• 工夫复杂度：O(n)，其中 n 是数组的长度。快指针和慢指针最多各挪动 n 次。
• 空间复杂度：O(1)。只须要应用常数的额定空间。