数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
举一个字符数组的例子，如图所示：
需要两点注意的是
数组下标都是从0开始的。
数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
例如删除下标为3的元素，需要对下标为3的元素后面的所有元素都要做移动操作，如图所示：
像Java是没有指针的，同时也不对程序员暴露其元素的地址，寻址操作完全交给虚拟机。
public static void test_arr() {
int[][] arr = {{1, 2, 3}, {3, 4, 5}, {6, 7, 8}, {9,9,9}};
System.out.println(arr[0]);
System.out.println(arr[1]);
System.out.println(arr[2]);
System.out.println(arr[3]);
}
[I@7852e922
[I@4e25154f
[I@70dea4e
[I@5c647e05
二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
提示： 你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。
思路
这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。
二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？
大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
下面我用这两种区间的定义分别讲解两种不同的二分写法。
第一种写法
我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：
while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
第二种写法
如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。
有如下两点：
while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
在数组：1,2,3,4,7,9,10中查找元素2，如图所示：（注意和方法一的区别）
public class BinarySearch {
// 左闭右闭
public static int search1(int[] nums, int target) {
// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
if (nums[0] > target || nums[nums.length - 1] < target) {
return -1;
}
int left = 0;
int right = nums.length-1;// 定义target在左闭右闭的区间里，[left, right]
while (left <= right) {// 当left==right，区间[left, right]依然有效，所以用 <=
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[middle] > target) {
right = middle - 1;// target 在左区间，所以[left, middle - 1]
}
else if (nums[middle] < target) {
left = middle + 1;// target 在右区间，所以[middle + 1, right]
}
else {
return middle;// 数组中找到目标值，直接返回下标
}
}
return -1;
}
// 左闭右开
public static int search2(int[] nums, int target) {
if (nums[0] > target || nums[nums.length - 1] < target) {
return -1;
}
int left = 0;
int right = nums.length;// 定义target在左闭右开的区间里，即：[left, right)
while (left < right) {// 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle;// target 在左区间，在[left, middle)中
}
else if (nums[middle] < target) {
left = middle + 1;// target 在右区间，在[middle + 1, right)中
}
else {
return middle;
}
}
return -1;
}
public static void main(String []args) {
int[] nums1 = {-1, 0, 3, 5, 9, 12};
int target1 = 9;
int[] nums2 = {-1, 0, 3, 5, 9, 12};
int target2 = 2;
int a1 = search1(nums1, target1);
int b1 = search2(nums1, target1);
int a2 = search1(nums2, target2);
int b2 = search2(nums2, target2);
System.out.println("返回值a1为：" + a1);
System.out.println("返回值b1为：" + b1);
System.out.println("返回值a2为：" + a2);
System.out.println("返回值b2为：" + b2);
}
}
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
暴力解法
这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
时间复杂度：O(n^2)
空间复杂度：O(1)
双指针法
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置
时间复杂度：O(n)
空间复杂度：O(1)
public class RemoveElement {
//暴力解法
public static int removeElement(int[] nums, int val) {
int size = nums.length;
System.out.println(size);
for (int i = 0; i < size; i++){
if (nums[i] == val) {// 发现需要移除的元素，就将数组集体向前移动一位
for(int j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
i--;
size--;
System.out.println(size);
}
}
return size;
}
//快慢指针
public static int removeElement2(int[] nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.length; fastIndex++){
if (nums[fastIndex] != val) {
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
return slowIndex;
}
//移动次数最少
public static int removeElement3(int[] nums, int val) {
int leftIndex = 0;
int rightIndex = nums.length - 1;
while (leftIndex <= rightIndex) {
// 找左边等于val的元素
while (leftIndex <= rightIndex && nums[leftIndex] != val){
++leftIndex;
}
// 找右边不等于val的元素
while (leftIndex <= rightIndex && nums[rightIndex] == val) {
-- rightIndex;
}
// 将右边不等于val的元素覆盖左边等于val的元素
if (leftIndex < rightIndex) {
nums[leftIndex++] = nums[rightIndex--];
}
}
return leftIndex; // leftIndex一定指向了最终数组末尾的下一个元素
}
public static void main(String[] args) {
int[] nums1 = {3,2,2,3};
int val1 = 3;
int a = removeElement2(nums1, val1);
System.out.println("第一个测试用例的解为："+a);
int[] nums2 = {0,1,2,2,3,0,4,2};
int val2 = 2;
int b = removeElement2(nums2, val2);
System.out.println("第二个测试用例的解为："+b);
}
}
有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]
思路
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
如果A[i] * A[i] < A[j] * A[j] 那么result[k–] = A[j] * A[j]; 。
如果A[i] * A[i] >= A[j] * A[j] 那么result[k–] = A[i] * A[i]; 。
此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。
这里还是说一下，大家不必太在意leetcode上执行用时，打败多少多少用户，这个就是一个玩具，非常不准确。
做题的时候自己能分析出来时间复杂度就可以了，至于leetcode上执行用时，大概看一下就行，只要达到最优的时间复杂度就可以了，
一样的代码多提交几次可能就击败百分之百了…
双指针解法
import java.util.Arrays;
public class SortedSquares {
public static int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int[] result = new int [nums.length];
int index = result.length - 1;
while (left<=right) {//相等的时候也要更新，所以有等于号
if (nums[left] * nums[left] > nums[right] * nums[right]) {
result[index--] = nums[left] * nums[left++];
}
else if (nums[left] * nums[left] <= nums[right] * nums[right]) {
result[index--] = nums[right] * nums[right--];
}
}
return result;
}
public static void main(String[] args) {
int[] nums1 = {-4,-1,0,3,10};
int[] a = sortedSquares(nums1);
System.out.println("第一个测试用例的解为："+Arrays.toString(a));
int[] nums2 = {-7,-3,2,3,11};
int[] b = sortedSquares(nums2);
System.out.println("第二个测试用例的解为："+Arrays.toString(b));
}
}
