1.合并两个有序数组（88-易）
题目描述：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
示例：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6]
思路：本题比较简单的思路是：进行拼接然后再排序（插入排序或库函数）或者使用额外空间进行存储（使用for循环或者库函数）
System.arraycopy(dataType[] srcArray,int srcIndex,int destArray,int destIndex,int length)
其中，srcArray 表示源数组；srcIndex 表示源数组中的起始索引；destArray 表示目标数组；destIndex 表示目标数组中的起始索引；length 表示要复制的数组长度。
这里最优解是三指针，利用数组有序性，原地的排序，即不使用额外空间。
- 关键是使用从尾向头开始遍历（三指针）
- 注意，这时谁大谁先走！
代码：
public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1, j = n - 1, merge = m + n - 1; while (i >= 0 || j >= 0) { if (i < 0) { nums1[merge--] = nums2[j--]; } else if (j < 0) { nums1[merge--] = nums1[i--]; } else if (nums1[i] > nums2[j]) { nums1[merge--] = nums1[i--]; } else { nums1[merge--] = nums2[j--]; } } }
2.下一个排列（31-中）
题目描述：实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。要求：必须 原地 修改，只允许使用额外常数空间。
示例：
输入：nums = [1,2,3] 输出：[1,3,2] 输入：nums = [3,2,1] 输出：[1,2,3]
思路：本题目标是找下一个更大的排列，双指针，我们可以将算法分为两步：
- 逆序遍历，当第一次出现
nums[i] < nums[i + 1]，记录此时的i为index2；然后我们去之前遍历中第一个比nums[i]大的数对应的索引index2，交换。 - 我们已经替换了
i位置的数，但其后的数一定降序（之前遍历过），根据字典序，我们要将i后边的数逆序。
ps：为什么逆序遍历，目的是找最后一个出现升序的元素，然后找刚好比他大的第一个元素替换，符合字典序。
代码：
public void nextPermutation(int[] nums) { int index1 = -1, index2 = -1; for (int i = nums.length - 2; i >= 0; i--) { if (nums[i] < nums[i + 1]) { index1 = i; break; } } // 特判 if (index1 == -1) { reverse(nums, 0, nums.length - 1); return; } for (int i = nums.length - 1; i > index1; i--) { if (nums[i] > nums[index1]) { index2 = i; break; } } swap(nums, index1, index2); reverse(nums, index1 + 1, nums.length - 1); } public void reverse(int[] nums, int i, int j) { while (i < j) { swap(nums, i++, j--); } } public void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }
3.盛最多水的容器（11-中）
题目描述：给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例：
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 输入：height = [1,1] 输出：1
思路：
法1：暴力求解，时间复杂度O(n^2)，注意：盛水木桶效应。但是遗憾的是超时了。
法2：本题的最优解是双指针，代码简单，主要是理解为什么这样可以：背后思想缩减空间，当双指针位于最两端，这是水的宽度最大：
- 如果左边的高度小，我们移动左指针（移除左边一个柱子），那问题就是，右指针移动的那些就不考虑了吗？其实，由于左边柱子高度低，所以这是个瓶颈，无论怎么移动右指针，都不会比现在的面积大（宽度在减少）。但是如果移动左指针，那么虽然宽度变小了，但是高度可能增大，这带来了不确定性，需要我们去判断。
- 同理移除右边一个柱子，分析相同。
代码：
// 暴力解 public int maxArea(int[] height) { int n = height.length; int max = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { max = Math.max(max, Math.min(height[i], height[j]) * (j - i)); } } return max; } // 双指针 public int maxArea(int[] height) { int l = 0, r = height.length - 1; int max = 0; while (l < r) { max = height[l] < height[r] ? Math.max(max, (r - l) * height[l++]): Math.max(max, (r - l) * height[r--]); } return max; }
4.颜色分类（75-中）
题目描述：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
思路：本题本质是荷兰国旗问题（快排的分区过程），在荷兰国旗中，我们是给定值num，判断数组中的值与num的大小，进而确定自己的位置。cur指针负责遍历数组，时间复杂度O(n)。定义两个边界指针zero和two，遍历数组跟新这两个边界。
- 当前值等于0，相当于推着大于0的部分向后走
- 当前值等于1（中间元素），cur指针移动
- 当前值等于2，需要用后边值进行交换后继续比较
代码：
public void sortColors(int[] nums) { int zero = -1, two = nums.length; int cur = 0; while (cur < two) { if (nums[cur] == 0) { swap(nums, ++zero, cur++); } else if (nums[cur] == 2) { swap(nums, --two, cur); } else { cur++; } } } public void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }
5.将数组分成和相等的三个部分（1013-易）
题目描述：给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
形式上，如果可以找出索引 i+1 < j 且满足 A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1] 就可以将数组三等分。
示例：
输入：[0,2,1,-6,6,-7,9,1,2,0,1] 输出：true 解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
思路： 本题先计算数组的总和，如果不能被3整除，直接返回false，否则：
法1：使用双指针遍历，注意遍历终止条件，为 l + 1 < r ，保证数组被划分为三个部分，也就是中间有一个元素的情况。注意细节：左右和初始值设为第一个元素，否则指针提前结束的指针会多移动一次，可能提前退出循环，如[3,3,6,5,-2,2,5,1,-9,4]，返回false。
法2：直接查找，当等于target的个数为3，则一定能被分成三部分。其实，可能存在这个个数大于3的情况（目标值target为0的情况），但是我们可以提前终止，否则总和不为0，也就不会出现个数大于3的情况。
代码：
// 双指针 public boolean canThreePartsEqualSum(int[] nums) { int n = nums.length; int sum = 0; for (int num : nums) { sum += num; } if (sum % 3 != 0) { return false; } int target = sum / 3; int l = 0, r = n - 1; int lSum = nums[l], rSum = nums[r]; while (l + 1 < r) { if (lSum == target && rSum == target) { return true; } if (lSum != target) { lSum += nums[++l]; } if (rSum != target) { rSum += nums[--r]; } } return false; } } // 直接查找 public boolean canThreePartsEqualSum(int[] nums) { int n = nums.length; int sum = 0; for (int num : nums) { sum += num; } if (sum % 3 != 0) { return false; } int target = sum / 3; int flag = 0; int curSum = 0; for (int num : nums) { curSum += num; if (curSum == target) { flag++; curSum = 0; } if (flag == 3) { return true; } } return false; }
6.有序数组的平方（977-易）
题目描述：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]
思路：核心考察点是利用原数组有序，但是可以通过这个题练习一下常见的排序算法。
最优解为双指针，因为结果最大值一定出现在原数组最大值或者最小值，故可以直接使用两个指针从两头进行遍历。
代码：
// 直接调库函数 public int[] sortedSquares(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { nums[i] = nums[i] * nums[i]; } Arrays.sort(nums); return nums; } // 双指针 public int[] sortedSquares(int[] nums) { int n = nums.length; int index = n - 1; int[] ans = new int[n]; for (int i = 0, j = n - 1; i <= j; ) { if (nums[i] * nums[i] > nums[j] * nums[j]) { ans[index--] = nums[i] * nums[i]; i++; } else { ans[index--] = nums[j] * nums[j]; j--; } } return ans; }
7.按奇偶排序数组 II（922-易）
题目描述：给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7] 输出：[4,5,2,7] 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
思路：本题两种解法，适用两种情况。
法1：可以使用额外空间。两遍遍历，奇数放在新数组奇数位置，偶数放在新数组偶数位置。
法2：不使用额外空间，可以原地修改数组。使用奇偶指针，遍历数组，寻找两个都没放对位置的，交换两个数。
代码：
// 两遍遍历 public int[] sortArrayByParityII(int[] nums) { int n = nums.length; int[] tmp = new int[n]; int index = 0; for (int i = 0; i < n; i++) { if (nums[i] % 2 == 0) { tmp[index] = nums[i]; index += 2; } } index = 1; for (int i = 0; i < n; i++) { if (nums[i] % 2 == 1) { tmp[index] = nums[i]; index += 2; } } return tmp; } // 快慢指针 public int[] sortArrayByParityII(int[] nums) { int n = nums.length; int j = 1; for (int i = 0; i < n; i += 2) { if (nums[i] % 2 == 1) { while (nums[j] % 2 == 1) { j += 2; } swap(nums, i, j); } } return nums; } public void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }
