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;
}