977. Squares of a Sorted Array

題目連結

思路

此題主要想傳達的概念是雙指標的運用，因為題目本身用比較暴力直觀的方式來解的話並不複雜，將輸入陣列的數字遍歷一遍並且平方過後，再重新排序即可得到題目所求。

使用雙指標可以讓演算法運作的時候一邊進行平方的運算，一邊完成排序的處理，時間複雜度會壓在 $O(n)$。而此題的關鍵點在於輸入序列是已經排序好的數值 (包含正、負數)，因此平方過後最大的數一定會出現在左右兩個極端，因此可以將兩個指標分別放在左右兩端，逐步往中間處理計算，每一步都會比較左右兩端的平方數何者較大，並把比較大的那邊丟到新的陣列裡面然後往裡面前進一格，直到左右兩邊的指標碰在一起就代表結束運算。

在 Go 裡面可以用比較簡潔的方式來撰寫 for 迴圈，在宣告條件時就可以一次把左右指標和新陣列的指標一起帶進去，而一般的 while 迴圈在 Go 當中也是使用 for 這個 keyword 來處理。另一點是由於此題的輸出是一個和原始陣列一樣長度的陣列，因此在這邊可以直接使用 for 迴圈，等到 idx 走完的同時也填完了新的陣列，結束遍歷。

Full Code

Golang

func sortedSquares(nums []int) []int {
    l := len(nums)
    newNums := make([]int, l)

    for left, right, idx := 0, l - 1, l - 1; idx >= 0; idx-- {
        leftSquare := nums[left] * nums[left]
        rightSquare := nums[right] * nums[right]

        if leftSquare <= rightSquare {
            newNums[idx] = rightSquare
            right--
        } else {
            newNums[idx] = leftSquare
            left++
        }
    }

    return newNums
}