27. Remove Element

題目描述：

給定一個陣列 nums 和一個值 val，你需要原地移除所有數值等於 val 的元素，並返回移除後陣列的新長度。

不要使用額外的陣列空間，必須在 O(1) 額外空間的條件下完成此操作。

元素的順序可以改變。你不需要考慮陣列中超出新長度後面的元素。

解題思路:
這道題目與之前的第 26 題「Remove Duplicates from Sorted Array」非常相似，解題方式同樣採用「雙指針」（Two Pointers）。雖然我們可以使用相同的解法來解決，但這未免有些無趣，有沒有更高效的解法呢？答案是肯定的。

為了提升效率，我們這次不再讓雙指針同時從頭開始，而是從陣列的兩端進行操作。首先，我們初始化兩個指針：i 從陣列開頭開始，n 則標記陣列的有效長度。在遍歷過程中，如果 nums[i] 等於 val，我們將其與陣列末尾的元素交換，並將有效長度 n 減少 1。這樣可以確保 val 被移到陣列末尾。而當 nums[i] 不等於 val 時，我們直接移動指針 i，繼續檢查下一個元素。需要注意的是，指針 i 只在當前元素不等於 val 時才會移動，這樣交換後的元素也能被正確檢查。最後，我們返回 n，它代表移除 val 後陣列的新長度。

var removeElement = function(nums, val) {
    let n = nums.length;

    for (let i = 0; i < n; ) {
        if (nums[i] === val) {
            nums[i] = nums[n - 1];
            n--;
        } else {
            i++;
        }
    }

    return n;
};

時間複雜度：O(n)，其中 n 是陣列的長度。在最壞的情況下，陣列中的每個元素最多只會被交換一次或被跳過一次。
空間複雜度：O(1)，我們只使用了常數空間來存儲指針。

總結:
這道題目可以歸類為「Two Pointers」。與第 26 題「Remove Duplicates from Sorted Array」相比，雙指針可以有兩種不同的使用方式：一種是同時從頭開始，另一種是從兩端開始。這兩種方法的時間複雜度和空間複雜度都是相同的，但從兩端開始的方法可能更快，因為它在找到要移除的元素後，立即將其與最後一個元素交換，並減少陣列長度，從而減少遍歷次數，提升效率。不過，這種方法的缺點是元素的順序將不再與原始陣列一致。如果題目要求保持順序，則應使用從頭開始的解法。藉由這兩題 LeetCode，我們體驗了兩種不同的 Two Pointers 解題方式。建議讀者不僅要掌握這兩種方法，還要理解它們之間的差異，這將有助於在不同情境下靈活應用。