题目：
给你一个数组 nums 和一个值 val，你须要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要应用额定的数组空间，你必须仅应用 O(1) 额定空间并 原地 批改输出数组。
元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
题解：
首先，这是一道数组类的简略算法题。咱们明确循环不变式（loop invariant）的概念，即一组在循环体内、每次迭代均放弃为真的性质。
先贴代码：（GO语言）
func removeElement(nums []int, val int) int { left, right, n := 0, 0, len(nums) for right < n { if nums[right] != val { nums[left] = nums[right] left++ } right++ } return left}咱们设置的循环不变式：left指针之前的数组元素（不蕴含目前所指元素）不为val。
- 初始
left设为0，即nums[0]之前的元素不为val，因为nums[0]之前没有元素，left地位满足不变式要求。 - 接下来的循环中，如果
nums[right]不为val，则将nums[right]赋值给nums[left]后后移left，完结本次循环。如果nums[right]为val，则间接完结本次循环。每次循环，left地位均满足不变式要求。 - 最终
right指针遍历完数组元素后，完结整个循环，left地位满足不变式要求。
因而在循环完结后，left左侧元素均为非val元素，合乎算法要求。
复杂度剖析：
- 工夫复杂度：
O(n)，其中n为序列长度。每个地位至少被遍历两次。 - 空间复杂度：
O(1)。只须要常数的空间寄存若干变量。
优化：
咱们留神到，题目中还有一个阐明，“元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素”，也就是说，咱们能够通过放弃原数组元素的地位不变来缩小赋值次数。
当val非常少的时候，原办法会呈现大量的冗余赋值，缩小赋值次数是对性能的一个大的晋升。
先贴代码：（GO语言）
func removeElement(nums []int, val int) int { left, right := 0, len(nums)-1 for right >= left { if nums[right] != val { nums[left], nums[right] = nums[right], nums[left] left++ } else { right-- } } return left}同样，咱们的循环不变量放弃不变，即left指针之前的数组元素（不蕴含目前所指元素）不为val。设置数组首尾指针，循环终止条件为right >= left以保障所有元素均被遍历过一次。循环中保护不变式，最终后果满足题目要求。
复杂度剖析：
- 工夫复杂度：
O(n)，其中n为序列长度。每个地位至少被遍历一次。 - 空间复杂度：
O(1)。只须要常数的空间寄存若干变量。