数组和字符串
一、数组介绍
集合、列表和数组
集合一般被定义为：由一个或多个确定的元素所构成的整体。首先，**集合里的元素类型不一定相同。**其次，集合里的元素没有顺序。
列表（又称线性列表）的定义为：是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。
数组是列表的实现方式之一，也是面试中经常涉及到的数据结构。
数组有索引，列表没有索引。
集合：无序
列表：有序，没有索引，内存地址可以连续，也可以不连续
数组：有索引，内存是连续的
数组的操作
读取，我们直到索引为0的元素的地址，在这个基础上加上索引值，读取相应元素
查找，因为我们只知道索引为0元素的地址，所以我们只有遍历，才能判断所有存在目标元素
插入，分两种，一种是插入在尾部，这个直接插入；如果是插入在数组中间，这样就需要在中间为元素腾出位置，在插入
删除，删除类似，删除尾部和删除中间元素的区别。
724. 寻找数组的中心下标
Details
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例 1：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。示例 2：
输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。示例 3：
输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。如果直接去思考问题的话，可能会陷入一个错误的方向，如果换个思路，就很快解决。
问题是找到下标i，sum(0, i-1) == sum(i+1, n-1)， 可以转换成 2 * sum(0, i-1) == sum - nums[i]
class Solution {
public int pivotIndex(int[] nums) {
int sum = 0;
for(int x: nums){
sum += x;
}
int suml = 0;
for(int i = 0;i<nums.length;i++){
if(2*suml == (sum-nums[i])){
return i;
}
suml+=nums[i];
}
return -1;
}
}35. 搜索插入位置
Details
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4class Solution {
public int searchInsert(int[] nums, int target) {
// O(logn) 二分
int n = nums.length;
int l = 0;
int r = n - 1;
while (l <= r) {
int mid = (r - l) / 2 + l;
int t = nums[mid];
if (t == target) {
return mid;
} else if (t > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
}
}O(logn)一看就是二分的大方向。