前言

在軟體工程師和程式設計的工作或面試的過程中不會總是面對到只有簡單邏輯判斷或計算的功能，此時就會需要運用到演算法和資料結構的知識。本系列文將整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 Python）。其中字串處理操作是程式設計日常中常見的使用情境，本文繼續將從簡單的陣列和串列處理問題開始進行介紹。

要注意的是在 Python 並無 Array 陣列的資料型別，主要會使用 List 串列進行說明。不過，相對於一般程式語言的 Array 陣列，Python 串列 List 具備許多彈性和功能性。

舉例來說，切片 slicing 就是 Python List 非常方便的功能，可以很方便的取出指定片段的子串列：

names = ['Jack', 'Joe', 'Andy', 'Kay', 'Eddie']
sub_names = names[2:4]

print(sub_names)

執行結果：

['Andy', 'Kay']

常見問題

兩數之合

Problem: Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

本題考驗是給定一個目標值和一串整數陣列，希望找到兩數相加等於目標值的數字索引。

Solution
參考方法一：迴圈相加比較法
透過兩層迴圈依序測試相加是否等於目標值，若是則回傳兩者的 index 值。這是一種直觀的作法但相對較慢。由於需要進行兩層迴圈運算，所以時間複雜度 O(n^2)。

範例程式碼：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 透過兩層迴圈依序測試相加是否等於目標值，是直觀的作法但相對較慢。時間複雜度 O(n^2)
        # 第一層的數字和其餘數字相加並和目標值比較看看
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

參考方法二：簡化迴圈相加比較法
透過迴圈將數值和目標值相減後檢查差異值是否有在剩餘數組中，若有則取得兩數的索引值。這樣取得第二個數在剩餘數組的位置的方式可以簡化第一種方法兩層迴圈運算較慢的問題。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 透過迴圈將數值和目標值相減後檢查差異值是否有在剩餘數組中，若有則取得兩數的索引值
        for i in range(len(nums) - 1):
            if (target - nums[i]) in nums[i+1:]:
                # 取得第二個數在剩餘數組的位置
                j = nums[i+1:].index(target - nums[i])
                return [i, i + j + 1]

旋轉圖片

Problem: Rotate Image
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise 順時針).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Example 3:

Input: matrix = [[1]]
Output: [[1]]

Example 4:

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

Constraints:

matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

本題為給定一個 n x n 二維陣列代表一個圖片，將圖片順時針旋轉 90 度，注意需要在原地旋轉（修改原陣列）不要使用另外一個陣列來旋轉。

Solution
參考方法一：順時旋轉規律
將一個二維陣列 m[i,j] 旋轉後和原來的陣列進行比較，發現旋轉 90 度後規則為行列索引互換 m[j,i] 但排序相反這個規律。

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        # 將一個二維陣列 m[i,j] 旋轉後和原來的陣列進行比較，發現旋轉 90 度後規則為行列索引互換 m[j,i] 但排序相反
        for i in range(len(matrix)):
            for j in range(i + 1, len(matrix)):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # 排序反轉
        for i in range(len(matrix)):
            matrix[i].reverse()

        return

總結

以上介紹了常見的程式解題陣列相關問題，本系列文將持續整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 Python）。需要注意的是 Python 本身內建的操作方式、資料型別結構和其他程式語言可能不同，文中所列的不一定是最好的解法，讀者可以自行嘗試在時間效率和空間效率運用上取得最好的平衡點。