上篇我們了解陣列跟字串，再來就是最常見的觀念會在陣列與字串上操作，那就是 Two Pointers，關於這個主題的題目可以說是非常多，只是題目說明的時候並不會意識到 Two Pointers，但不知不覺我們已經在使用它。

來看看案例題目我們這次選擇 LeetCode 922. Sort Array By Parity II，這題規定要針對索引奇數要擺奇數，偶數索引數對應偶數，我們可以看原本題目範例說明。

範例：

輸入陣列: nums = [4,2,5,7]
輸出陣列: [4,5,2,7]
解釋: [4,7,2,5], [2,5,4,7], [2,7,4,5] 這三個結果也可以接受。

我們以 [4,2,5,7] 為例子使用 Two pointers，給它一個奇數指針跟偶數指針，讓它一個一個走訪。

[4, 2, 5, 7]
 ^  ^
 0  1

我們發現第一個位置為 4，第二個位置是 2，2 因為索引值是奇數，所以不符合，所以偶數索引值往前兩步。

[4, 2, 5, 7]
    ^  ^
    1  2

移動後發現 2 跟 5 不符合索引值奇數偶數定義，所以交換。

[4, 5, 2, 7]
    ^  ^
    1  2

[4, 5, 2, 7]
       ^  ^
       2  3

繼續走訪兩步發現索引值 3 但是值是 7，是符合條件，所以不做任何事。

我們就結束任務了！

所以 Swift 程式碼會如下呈現：

func sortArrayByParityII(_ nums: [Int]) -> [Int] {
    var nums = nums
    var i = 0
    var j = 1

    while i < nums.count && j < nums.count {
        if nums[i] % 2 == 0 {
            i += 2
        } else {
            if nums[j] % 2 != 0 {
                j += 2
            } else {
                let temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
            }
        }
    }
    return nums
}

時間複雜度：O(n)
空間複雜度：O(1)

另外一種常見寫法，會先建立 Array，一個一個走訪然後擺進新的 Array，但是因為我們新建一個 Array，導致空間複雜度變成 O(n)。

func sortArrayByParityII(_ nums: [Int]) -> [Int] {
    var result = Array(repeating: 0, count: nums.count)
    var evenIndex = 0
    var oddIndex = 1

    for num in nums {
        if num % 2 == 0 {
            result[evenIndex] = num
            evenIndex += 2
        } else {
            result[oddIndex] = num
            oddIndex += 2
        }
    }

    return result
}

總結

本題讓 Two pointers 的概念非常好理解，其實可以發現如果不用這個概念暴力搜尋的話，是有可能跑兩層迴圈，這樣反而讓時間複雜度大幅增加，但是我們因為套了 Two pointers 只需要一層迴圈，因此優化了時間複雜度。接下來我們可以開始研究 SwiftUI 與此題的結合呈現，讓我們一起期待吧。