数组
数组是数据结构中的基本模块之一。因为字符串是由字符数组形成的，所以二者是相似的。大多数面试问题都属于这个范畴。
在这张卡片中，我们将介绍数组和字符串。完成这张卡片后，我们将：
了解数组和动态数组之间的区别；
熟悉数组和动态数组中的基本操作；
理解多维数组并能够掌握二维数组的使用；
明白字符串的概念以及字符串所具有的不同特性；
能够运用双指针技巧解决实际问题。
数组是一种基本的数据结构，用于按顺序存储元素的集合。但是元素可以随机存取，因为数组中的每个元素都可以通过数组索引来识别。
数组可以有一个或多个维度。这里我们从一维数组开始，它也被称为线性数组。这里有一个例子：
在上面的例子中，数组 A 中有 6 个元素。也就是说，A 的长度是 6 。我们可以使用 A[0] 来表示数组中的第一个元素。因此，A[0] = 6 。类似地，A[1] = 3，A[2] = 8，依此类推。
下面是数组的用法
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
// 1. Initialize
int[] a0 = new int[5];
int[] a1 = {1, 2, 3};
// 2. Get Length
System.out.println("The size of a1 is: " + a1.length);
// 3. Access Element
System.out.println("The first element is: " + a1[0]);
// 4. Iterate all Elements
System.out.print("[Version 1] The contents of a1 are:");
for (int i = 0; i < a1.length; ++i) {
System.out.print(" " + a1[i]);
}
System.out.println();
System.out.print("[Version 2] The contents of a1 are:");
for (int item: a1) {
System.out.print(" " + item);
}
System.out.println();
// 5. Modify Element
a1[0] = 4;
// 6. Sort
Arrays.sort(a1);
}
}
动态数组简介
正如我们在上面中提到的，数组具有固定的容量，我们需要在初始化时指定数组的大小。有时它会非常不方便并可能造成浪费。
因此，大多数编程语言都提供内置的动态数组，它仍然是一个随机存取的列表数据结构，但大小是可变的。例如，在 C++ 中的 vector，以及在 Java 中的 ArrayList。
动态数组中的操作:
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
// 1. initialize
List<Integer> v0 = new ArrayList<>();
List<Integer> v1; // v1 == null
// 2. cast an array to a vector
Integer[] a = {0, 1, 2, 3, 4};
v1 = new ArrayList<>(Arrays.asList(a));
// 3. make a copy
List<Integer> v2 = v1; // another reference to v1
List<Integer> v3 = new ArrayList<>(v1); // make an actual copy of v1
// 3. get length
System.out.println("The size of v1 is: " + v1.size());;
// 4. access element
System.out.println("The first element in v1 is: " + v1.get(0));
// 5. iterate the vector
System.out.print("[Version 1] The contents of v1 are:");
for (int i = 0; i < v1.size(); ++i) {
System.out.print(" " + v1.get(i));
}
System.out.println();
System.out.print("[Version 2] The contents of v1 are:");
for (int item : v1) {
System.out.print(" " + item);
}
System.out.println();
// 6. modify element
v2.set(0, 5); // modify v2 will actually modify v1
System.out.println("The first element in v1 is: " + v1.get(0));
v3.set(0, -1);
System.out.println("The first element in v1 is: " + v1.get(0));
// 7. sort
Collections.sort(v1);
// 8. add new element at the end of the vector
v1.add(-1);
v1.add(1, 6);
// 9. delete the last element
v1.remove(v1.size() - 1);
}
}
小练习:
寻找数组的中心索引
给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。
我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
示例 1:
输入:
nums = [1, 7, 3, 6, 5, 6]
输出: 3
解释:
索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。
同时, 3 也是第一个符合要求的中心索引。
示例 2：
输入:
nums = [1, 2, 3]
输出: -1
解释:
数组中不存在满足此条件的中心索引。
说明:
nums 的长度范围为 [0, 10000]。
任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
代码实现：
class Solution {
public int pivotIndex(int[] nums) {
int len=nums.length;
int[] left=new int[len];
int[] right=new int[len];
left[0]=nums[0];
right[len-1]=nums[len-1];
for(int i=1;i<len;i++)
{
left[i]=left[i-1]+nums[i];
}
for(int i=len-2;i>=0;i--)
{
right[i]=right[i+1]+nums[i];
}
for (int i=0;i<len;i++) {
if(left[i]==right[i])
return i;
}
return -1;
}
}
下面是一个更优秀的做法，避开了多开辟两个数组的麻烦。那就是根据索引实时修改左边的值和右边的值的取值，如果相等直接返回答案。如果直到循环结束也没有遇到相等的则返回-1。
这样做是上一种写法的优化，省去了开辟数组用的内存空间。当然这里要注意左值和右值加减的顺序。
class Solution {
public int pivotIndex(int[] nums) {
int len=nums.length;
int right = 0;
int left = 0 ;
for (int i : nums) {
right+=i;
}
for(int i=0;i<len;i++)
{
right-=nums[i];
if(left==right)
return i;
left+=nums[i];
}
return -1;
}
}
练习2：至少是其他数字两倍的最大数
在一个给定的数组nums中，总是存在一个最大元素 。
查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
如果是，则返回最大元素的索引，否则返回-1。
示例 1:
输入: nums = [3, 6, 1, 0]
输出: 1
解释: 6是最大的整数, 对于数组中的其他整数,
6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.
示例 2:
输入: nums = [1, 2, 3, 4]
输出: -1
解释: 4没有超过3的两倍大, 所以我们返回 -1.
提示:
nums 的长度范围在[1, 50].
每个 nums[i] 的整数范围在 [0, 99].
解决方案：
待定
