算法（3）：数组

一鼓作气，再而衰，三而竭，第三篇走起！

目录：
算法：附录
 算法（1）：递归
 算法（2）：链表
 算法（3）：数组
 算法（4）：字符串
 算法（5）：二叉树
 算法（6）：二叉查找树
 算法（7）：队列和堆栈（附赠BFS和DFS）
算法（8）：动态规划
 算法（9）：哈希表
 算法（10）：排序
 算法（11）：回溯法
 算法（12）：位操作

数组（Array）

数组是大家再熟悉不过的东西了，但是这里还是简单说一下，数组是连续存放一系列元素的数据结构，我们可以方便的通过索引访问数组当中的任何一个元素。通常，数组在定义时是固定大小的，但是也有一种动态数组，它在初始化时不需要定义数组大小，也就意味着可以无限装数据，我们称之为动态数组，如C++当中的Vector（曾经是我最喜欢的一个数据结构，当然，在我遇到python当中的List之前）和Java当中的ArrayList 。

安利一波问题4，大家一定要看一看。

问题1：找到一个一维数组的“中枢”元素的索引。如果有很多中枢元素，则只需返回最左侧的即可。中枢在此处意味着该索引左侧元素和等于该索引右侧元素和。
输入: [1, 2, 8, 4, 5, 6]
输出: 3（1+2+8 = 5+6）

代码，那是异常的简单啊。小编不禁想起了有一次面试，面试官让我写一个找数组中最大最小值的算法，啊，那时的时光是多么美好！如下代码的时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。

def pivotIndex(nums) -> int:
    ts, cs = sum(nums), 0
    for idx, num in enumerate(nums):
        ls, rs = cs, ts - cs - num
        if ls == rs:
            return idx
        cs += num
    return -1

if __name__ == '__main__':
    ans = pivotIndex([1, 2, 8, 4, 5, 6])
    print(ans)

问题2：加1操作。将输入数组当成一个整数，然后执行加1操作
例子：
输入: [1,2,3] 输出: [1,2,4]
输入: [9,9,9] 输出: [1,0,0,0]

我的方法是直接在数组里面执行操作，当然你也可以换种方法，如把数组里元素按位读出来变成int，然后加一，然后在按位存放到数组中。

def plusOne(digits: list) -> list:
    digits = [0] + digits
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] == 9:
            digits[i] = 0
        else:
            digits[i] += 1
            break

    return (digits, digits[1:])[0 if digits[0] != 0 else 1]

if __name__ == '__main__':
    ans = plusOne([1, 2, 8, 4, 5, 6])
    print(ans)

问题3：对角线遍历二维数组(Diagonal Traverse)。
一维数组一般都很简单，但是到了二维数组，难度就会上升一个台阶，毕竟，问题的花样变多了嘛~
输入:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
输出: [1,2,4,7,5,3,6,8,9]
如果看不懂的话，可以配上下面这张图看，保证一眼就明白~

对角线遍历矩阵图

代码具体思路分为两步：
step1：根据对角线将矩阵分组（可以发现，同一对角线的矩阵row和col坐标相加为定值），如上图，可以分为5组，得到[1] , [2,4]，[3,5,7]，[6,8]，[9]。
step2：按照（row + col）的大小顺序将数据依次添加到结果列表当中。根据代码定义，在（row + col ）为偶数时，需要翻转一下该组元素。即[3,5,7]（此时row + col = 2）需要变为[7,5,3]再添加到结果中。

import  collections
def findDiagonalOrder(matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[int]
    """
    result = []
    dd = collections.defaultdict(list)
    if not matrix: return result
    # Step 1: Numbers are grouped by the diagonals.
    # Numbers in same diagonal have same value of row+col
    for i in range(0, len(matrix)):
        for j in range(0, len(matrix[0])):
            dd[i + j].append(matrix[i][j])  # starting indices from 1, hence i+j+1.
    # Step 2: Place diagonals in the result list.
    # But remember to reverse numbers in odd diagonals.
    for k in sorted(dd.keys()):
        if k % 2 == 0: dd[k].reverse()
        result += dd[k]
    return result

if __name__ == '__main__':
    arr = [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]
    ans = findDiagonalOrder(arr)
    print(ans)

问题4：旋转矩阵（Spiral Matrix），即返回一个矩阵顺时针旋转的结果。
输入：
[ [ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ] ]
输出：[1,2,3,6,9,8,7,4,5]

下面这个答案是我在网上找的，看到这个代码之后的好久时间里，我的嘴巴只能发出“wo cao”这两个音。。。看到这段代码，我仿佛恋爱了。

def spiralOrder(matrix: list) -> list:
    return matrix and [*matrix.pop(0)] + spiralOrder([*zip(*matrix)][::-1])

if __name__ == '__main__':
    arr = [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]
    ans = spiralOrder(arr)
    print(ans)

问题5：数组求和。给定一个升序排列的数组，找出两个数，其和等于输入‘target’，结果返回这两个数的索引。
输入: numbers = [2,7,11,15], target = 9
输出: [1,2]
我们如果使用暴力法的话，结果有 $C^2_n$ 种，时间复杂度为 $O(n^2)$ 。那么大家还记不记得 ~~有一招从天而降的掌法...~~ 上一章讲解的双指针技术呢？这里便用到了！两个指针分别从左和右开始向中间走，两个数的和大了，右指针左移，和偏小，左指针右移......

# 四个问题不吉利，小编拍胸脯保证，马上（百年之内）把第五个问题补起来！
def twoSum(numbers: list, target: int) -> list:
    i, j = 0, len(numbers) - 1
    while i < j:
        if numbers[i] + numbers[j] == target:
            return [i, j]
        elif numbers[i] + numbers[j] > target:
            j -= 1
        else:
            i += 1
    return []

if __name__ == '__main__':
    numbers = [2, 7, 11, 15]
    target = 9
    ans = twoSum(numbers,target)
    print(ans)

问题6：移除特定值（写五道已经达到我的标准了，奈何又看到一个较为经典的案例，那就......再来个双指针教学吧~），将数组当中等于’target'的值移除掉，空间复杂度限定为 $O(1)$ ，最后结果返回新数组长度。
例子：
输入：[1,2,7,4,4,5],target = 4
输出：4 （新数组为[1,2,7,5]，所以长度为4）
快指针遍历数组，慢指针则作为新数组的尾部。只有当快指针所指的值和‘target’不同时，才会执行赋值以及p+=1操作，相同时直接跳过该数。

def removeElement(numbers: list, target: int) -> int:
    p = 0
    for i in range(len(numbers)):
        if numbers[i] != target:
            numbers[p] = numbers[i]
            p +=1
    return p

if __name__ == '__main__':
    numbers = [1,7,3,4,4,5]
    target = 4
    ans = removeElement(numbers,target)
    print(ans)
    print(numbers[:ans])

问题7:满足要求的最小子数组(Minimum Size Subarray Sum)。不好意思我忍不住又添了一道......该题给定n只包含正整数的数组，以及一个整数s，要求是找到一个最小长度的连续子数组，该子数组的元素和≥s。如果不存在，则返回0。
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2（子数组 [4,3] 是满足题目约束的最小数组）
运行下面程序会输出每步变量信息，大家可以自己读读试试，看能否理解~如果不理解可以留言探讨，现在已经晚上11点了，小编扛不住，这道题就不写分析了......

def minSubArrayLen( s: int, nums: list) -> int:
    total = left = 0
    result = len(nums) + 1
    for right, num in enumerate(nums):
        total += num
        while total >= s:
            result = min(result, right - left + 1)
            total -= nums[left]
            left += 1
            print('total:',total,'result:',result,'left:',left,'right:',right)
    return result if result <= len(nums) else 0

if __name__ == '__main__':
    numbers = [2,3,1,2,4,3]
    target = 7
    ans = minSubArrayLen(target,numbers)
    print(ans)