【LeetCode】Array

本文会提到做 array 常犯错误、如何避免，与常见的技巧。
此系列 Leetcode 篇不介绍基本资料结构。
[toc]

常见错误：复制到 list 的 reference

通常出现在 2d array，改动其中一个 list，其他 item 若有同 reference 也会一起变动。
新手很容易踩这种坑，然後 debug 底不出来。

时机

1. 复制 sublist
   nums[len(nums) - m:] = nums[:m]
   改成 nums[len(nums) - m:] = nums[:m].copy()
2. 2d list 初始化 (matrix)
   mylist = [[0] * 3 ] * 9
   改成 mylist = [[0] * 3 for _ in range(9)]
3. 2d dp 阵列

掌握基础先备知识

为了避免踩这些不好除错的雷，
请务必要弄懂 深浅复制、pass by copy of reference 等等 Python 基础。

常见错误：index out of bound

写程序第一个碰到的错误？
基础但恼人。

平时多动脑：边界练习

除了多写以外，我没事会做个边界练习（？，不要养成用 run 来验证边界的坏习惯。
当发现某个题目写到超界的时候，就可以拿来练习各种转换一下，
这个回圈跑几次、i 的范围、换成 1 based 会怎麽跑？
例如：
given for i in range(9)
i = [0, 8]
这个回圈会跑 9 次
相等於
for i in range(0, 9)
如果 index 从 1 开始，
for i in range(1, 10)

还可以想想 <= 、 < 的转换 或 while 与 for 的转换
最好练到後期都不要喷边界错误。

Two pointers

这不是什麽演算法，就只是用两个指针指到的数值做处理。
我自己缩小这个定义范围，只有输入一个阵列，从头尾同时取用阵列的问题，才算阵列的 two pointers。
重点是在看题目时，要意识到比起从头到尾做，「两边一起做」或许比较好。
为什麽要两边一起做？可能阵列已经有排序过。
目标的数字要马在 left pointer 的右边，要马在 right pointer 的左边，两边同时看比较快
所以时间至少 O(NlogN)除非输入早已排序。
167. Two Sum II - Input array is sorted
做过题目就会知道最快用 hashmap，但 two pointers 好处是不需额外空间

binary search 是个 two pointers 的应用。

除了排序好的，也有其他情形可能需要利用左右指针，并适当往内缩减的状况：
11. Container With Most Water

Sliding window

减少重复做的事情。
最常碰到问题需要取 substring 做处理。
3. Longest Substring Without Repeating Characters

总结

今天不舒服先这样，明天再来多修多补齐一些思路。

发现写一写已经有点忘记几个月前的自己是怎麽想的了，
即使还记得曾经的 struggle，
开始有点变成某个思考是理所当然，
希望能在忘记之前都记下来。