Arrays and Strings

数组是数据结构中的基本模块。因为字符串是由字符串数组组成的，所以二者相似，大多数面试题目都属于这个范畴。

作为最简单的一种数据结构，它占据了一块连续的内存并按照顺序存储数据。创建数组时，我们需要首先指定数组的容量大小，然后根据大小分配内存。即使我们只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此数组的空间效率不是很好，经常会有空闲的区域没有得到充分利用。

由于数组中的内存是连续的，于是可以根据下标在 O(1) 时间读/写任何元素，因此它的时间效率是很高的。我们可以根据数组时间效率高的优点，用数组来实现简单的哈希表：把数组的下标设为哈希表的键值（Key），而把数组中的每一个数字设为哈希表的值（Value），这样每一个下标及数组中该下标对应的数字就组成了一个”键值-值”的配对。有了这样的哈希表，我们就可以在 O(1) 的时间内实现查找。从而快速、高效解决很多问题。

先来一道题目 1991.find the middle index in array。解法如下：

func findMiddleIndex(nums []int) int {
	ans := 0
	height := len(nums)
 
	if height < 2 {
		return ans
	}
 
	totalSum := 0
	for _, num := range nums {
		totalSum += num
	}
 
	leftSum := 0
 
	for i := 0; i < len(nums); i++ {
		rightSum := totalSum - leftSum - nums[i]
		if leftSum == rightSum {
			return i
		}
		leftSum += nums[i]
	}
 
	return -1
}

其实我第一次的解法很土，而且没有过。这里面有一个逻辑，rightSum := totalSum - leftSum - nums[i] 这行代码出现了我的思维逻辑！！！