第3章 数组中的问题其实最常见
面试中的算法问题，有很多并不需要复杂的数据结构支撑。就是用数组，就能考察出很多东西了。其实，经典的排序问题，二分搜索等等问题，就是在数组这种最基础的结构中处理问题的。在这一章中，我们学习常见的数组中处理问题的方法。…
目录
3-1 从二分查找法看如何写出正确的程序
3-2 改变变量定义，依然可以写出正确的算法
3-3 在LeetCode上解决第一个问题 Move Zeros
3-4 即使简单的问题，也有很多优化的思路
3-5 三路快排partition思路的应用 Sort Colors
3-6 对撞指针 Two Sum II - Input Array is Sorted
3-7 滑动窗口 Minimum Size Subarray Sum
3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters
3-1 从二分查找法看如何写出正确的程序
二分查找法
思想：将查找的键值和数组的的中间键值作比较，如果被查找键值小于中间键值，就在左子数组中继续查找；如果大于中间键值，就在右子数组中继续查找；否则，中间键值就是要找的元素。
注意：对于有序数列，才能使用二分查找法（排序的作用）
循环不变量（Loop invariant）：所谓循环不变量是指一种在整个循环过程中保持不变的性质，必须在以下3种情况下均保持不变，且该性质在循环终止后能证明算法的正确性。
- 初始化（循环初始化后，循环条件测试前）
- 迭代（第n次迭代后，第n+1次迭代前）
- 结束（循环终止，即循环条件判断为false时）
注意：在使用循环的算法里面，可以通过循环不变量证明其正确性。
public class BinarySearch {
private BinarySearch(){}
public static int binarySearch(Comparable[] arr, int n, Comparable target){
int l = 0, r = n - 1; // 在[l...r]的范围里寻找target
while(l <= r){ // 当 l == r时,区间[l...r]依然是有效的
int mid = l + (r - l) / 2;
if(arr[mid].compareTo(target) == 0) return mid;
if(target.compareTo(arr[mid]) > 0)
l = mid + 1; // target在[mid+1...r]中; [l...mid]一定没有target
else // target < arr[mid]
r = mid - 1; // target在[l...mid-1]中; [mid...r]一定没有target
}
return -1;
}
public static void main(String[] args) {
int n = (int)Math.pow(10, 7);
Integer data[] = Util.generateOrderedArray(n);
long startTime = System.currentTimeMillis();
for(int i = 0 ; i < n ; i ++)
if(i != binarySearch(data, n, i))
throw new IllegalStateException("find i failed!");
long endTime = System.currentTimeMillis();
System.out.println("Binary Search test complete.");
System.out.println("Time cost: " + (endTime - startTime) + " ms");
}
}
public class Util {
private Util(){}
public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
assert n > 0 && rangeL <= rangeR;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = (int)(Math.random() * (rangeR - rangeL + 1)) + rangeL;
return arr;
}
public static Integer[] generateOrderedArray(int n) {
assert n > 0;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = i;
return arr;
}
}
3-2 改变变量定义，依然可以写出正确的算法
如何写出正确的程序（总结）
- 明确变量的含义
- 循环不变量
- 小数据量调试
- 大数据量测试
public class BinarySearch {
private BinarySearch(){}
public static int binarySearch(Comparable[] arr, int n, Comparable target){
int l = 0, r = n; // 在[l...r)的范围里寻找target
while(l < r){ // 当 l == r 时, 区间[l...r)是一个无效区间
int mid = l + (r - l) / 2;
if(arr[mid].compareTo(target) == 0) return mid;
if(target.compareTo(arr[mid]) > 0)
l = mid + 1; // target在[mid+1...r)中; [l...mid]一定没有target
else // target < arr[mid]
r = mid; // target在[l...mid)中; [mid...r)一定没有target
}
return -1;
}
public static void main(String[] args) {
int n = (int)Math.pow(10, 7);
Integer data[] = Util.generateOrderedArray(n);
long startTime = System.currentTimeMillis();
for(int i = 0 ; i < n ; i ++)
if(i != binarySearch(data, n, i))
throw new IllegalStateException("find i failed!");
long endTime = System.currentTimeMillis();
System.out.println("Binary Search 2 test complete.");
System.out.println("Time cost: " + (endTime - startTime) + " ms");
}
}
public class Util {
private Util(){}
public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
assert n > 0 && rangeL <= rangeR;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = (int)(Math.random() * (rangeR - rangeL + 1)) + rangeL;
return arr;
}
public static Integer[] generateOrderedArray(int n) {
assert n > 0;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = i;
return arr;
}
}
3-3 在LeetCode上解决第一个问题 Move Zeros
题目 LeetCode 283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
import java.util.*;
// 283. Move Zeroes
// https://leetcode.com/problems/move-zeroes/description/
// 时间复杂度: O(n)
// 空间复杂度: O(n)
class Solution {
public void moveZeroes(int[] nums) {
ArrayList<Integer> nonZeroElements = new ArrayList<Integer>();
// 将vec中所有非0元素放入nonZeroElements中
for(int i = 0 ; i < nums.length ; i ++)
if(nums[i] != 0)
nonZeroElements.add(nums[i]);
// 将nonZeroElements中的所有元素依次放入到nums开始的位置
for(int i = 0 ; i < nonZeroElements.size() ; i ++)
nums[i] = nonZeroElements.get(i);
// 将nums剩余的位置放置为0
for(int i = nonZeroElements.size() ; i < nums.length ; i ++)
nums[i] = 0;
}
public static void main(String args[]){
int[] arr = {0, 1, 0, 3, 12};
(new Solution()).moveZeroes(arr);
for(int i = 0 ; i < arr.length ; i ++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
3-4 即使简单的问题，也有很多优化的思路
import java.util.*;
// 283. Move Zeroes
// https://leetcode.com/problems/move-zeroes/description/
// 时间复杂度: O(n)
// 空间复杂度: O(n)
class Solution1 {
public void moveZeroes(int[] nums) {
ArrayList<Integer> nonZeroElements = new ArrayList<Integer>();
// 将vec中所有非0元素放入nonZeroElements中
for (int i = 0; i < nums.length; i++)
if (nums[i] != 0)
nonZeroElements.add(nums[i]);
// 将nonZeroElements中的所有元素依次放入到nums开始的位置
for (int i = 0; i < nonZeroElements.size(); i++)
nums[i] = nonZeroElements.get(i);
// 将nums剩余的位置放置为0
for (int i = nonZeroElements.size(); i < nums.length; i++)
nums[i] = 0;
}
public static void main(String args[]){
int[] arr = {0, 1, 0, 3, 12};
(new Solution1()).moveZeroes(arr);
for(int i = 0 ; i < arr.length ; i ++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
// 283. Move Zeroes
// https://leetcode.com/problems/move-zeroes/description/
//
// 原地(in place)解决该问题
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution2 {
public void moveZeroes(int[] nums) {
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
for(int i = 0 ; i < nums.length ; i ++)
if( nums[i] != 0 )
nums[k++] = nums[i];
// 将nums剩余的位置放置为0
for(int i = k ; i < nums.length ; i ++)
nums[i] = 0;
}
public static void main(String args[]){
int[] arr = {0, 1, 0, 3, 12};
(new Solution2()).moveZeroes(arr);
for(int i = 0 ; i < arr.length ; i ++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
// 283. Move Zeroes
// https://leetcode.com/problems/move-zeroes/description/
//
// 原地(in place)解决该问题
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution3 {
public void moveZeroes(int[] nums) {
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
// 同时, [k...i] 为 0
for(int i = 0 ; i < nums.length ; i ++)
if(nums[i] != 0)
swap(nums, k++, i);
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
public static void main(String args[]){
int[] arr = {0, 1, 0, 3, 12};
(new Solution3()).moveZeroes(arr);
for(int i = 0 ; i < arr.length ; i ++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
// 283. Move Zeroes
// https://leetcode.com/problems/move-zeroes/description/
//
// 原地(in place)解决该问题
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution4 {
public void moveZeroes(int[] nums) {
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
// 同时, [k...i] 为 0
for(int i = 0 ; i < nums.length ; i ++)
if(nums[i] != 0)
if(k != i)
swap(nums, k++, i);
else
k ++;
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
public static void main(String args[]){
int[] arr = {0, 1, 0, 3, 12};
(new Solution4()).moveZeroes(arr);
for(int i = 0 ; i < arr.length ; i ++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
课后作业：LeetCode 27、26、80
3-5 三路快排partition思路的应用 Sort Colors
题目：LeetCode 75. 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
// 75. Sort Colors
// https://leetcode.com/problems/sort-colors/description/
//
// 计数排序的思路
// 对整个数组遍历了两遍
// 时间复杂度: O(n)
// 空间复杂度: O(k), k为元素的取值范围
public class Solution1 {
public void sortColors(int[] nums) {
int[] count = {0, 0, 0}; // 存放0, 1, 2三个元素的频率
for(int i = 0 ; i < nums.length ; i ++){
assert nums[i] >= 0 && nums[i] <= 2;
count[nums[i]] ++;
}
int index = 0;
for(int i = 0 ; i < count[0] ; i ++)
nums[index++] = 0;
for(int i = 0 ; i < count[1] ; i ++)
nums[index++] = 1;
for(int i = 0 ; i < count[2] ; i ++)
nums[index++] = 2;
// 小练习: 自学编写计数排序算法
}
public static void printArr(int[] nums){
for(int num: nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {2, 2, 2, 1, 1, 0};
(new Solution1()).sortColors(nums);
printArr(nums);
}
}
// 75. Sort Colors
// https://leetcode.com/problems/sort-colors/description/
//
// 三路快速排序的思想
// 对整个数组只遍历了一遍
// 时间复杂度: O(n)
// 空间复杂度: O(1)
public class Solution2 {
public void sortColors(int[] nums) {
int zero = -1; // [0...zero] == 0
int two = nums.length; // [two...n-1] == 2
for(int i = 0 ; i < two ; ){
if(nums[i] == 1)
i ++;
else if (nums[i] == 2)
swap(nums, i, --two);
else{ // nums[i] == 0
assert nums[i] == 0;
swap(nums, ++zero, i++);
}
}
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i]= nums[j];
nums[j] = t;
}
public static void printArr(int[] nums){
for(int num: nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {2, 2, 2, 1, 1, 0};
(new Solution2()).sortColors(nums);
printArr(nums);
}
}
课后作业：LeetCode 88、215
3-6 对撞指针 Two Sum II - Input Array is Sorted
双索引技术（Two Points）
- 对撞指针
- 滑动窗口
题目：LeetCode 167. 两数之和II-输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
// 167. Two Sum II - Input array is sorted
// https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
//
// 暴力枚举法
// 时间复杂度: O(n^2)
// 空间复杂度: O(1)
public class Solution1 {
public int[] twoSum(int[] numbers, int target) {
if(numbers.length < 2 /*|| !isSorted(numbers)*/)
throw new IllegalArgumentException("Illegal argument numbers");
for(int i = 0 ; i < numbers.length ; i ++)
for(int j = i+1 ; j < numbers.length ; j ++)
if(numbers[i] + numbers[j] == target){
int[] res = {i+1, j+1};
return res;
}
throw new IllegalStateException("The input has no solution");
}
private boolean isSorted(int[] numbers){
for(int i = 1 ; i < numbers.length ; i ++)
if(numbers[i] < numbers[i-1])
return false;
return true;
}
private static void printArr(int[] nums){
for(int num: nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
printArr((new Solution1()).twoSum(nums, target));
}
}
// 167. Two Sum II - Input array is sorted
// https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
//
// 二分搜索法
// 时间复杂度: O(nlogn)
// 空间复杂度: O(1)
public class Solution2 {
public int[] twoSum(int[] numbers, int target) {
if(numbers.length < 2 /*|| !isSorted(numbers)*/)
throw new IllegalArgumentException("Illegal argument numbers");
for(int i = 0 ; i < numbers.length - 1 ; i ++){
int j = binarySearch(numbers, i+1, numbers.length-1, target - numbers[i]);
if(j != -1){
int[] res = {i+1, j+1};
return res;
}
}
throw new IllegalStateException("The input has no solution");
}
private int binarySearch(int[] nums, int l, int r, int target){
if(l < 0 || l > nums.length)
throw new IllegalArgumentException("l is out of bound");
if(r < 0 || r > nums.length)
throw new IllegalArgumentException("r is out of bound");
while(l <= r){
int mid = l + (r - l)/2;
if(nums[mid] == target)
return mid;
if(target > nums[mid])
l = mid + 1;
else
r = mid - 1;
}
return -1;
}
private boolean isSorted(int[] numbers){
for(int i = 1 ; i < numbers.length ; i ++)
if(numbers[i] < numbers[i-1])
return false;
return true;
}
private static void printArr(int[] nums){
for(int num: nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
printArr((new Solution2()).twoSum(nums, target));
}
}
// 167. Two Sum II - Input array is sorted
// https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
//
// 对撞指针
// 时间复杂度: O(n)
// 空间复杂度: O(1)
public class Solution3 {
public int[] twoSum(int[] numbers, int target) {
if(numbers.length < 2 /*|| !isSorted(numbers)*/)
throw new IllegalArgumentException("Illegal argument numbers");
int l = 0, r = numbers.length - 1;
while(l < r){
if(numbers[l] + numbers[r] == target){
int[] res = {l+1, r+1};
return res;
}
else if(numbers[l] + numbers[r] < target)
l ++;
else // numbers[l] + numbers[r] > target
r --;
}
throw new IllegalStateException("The input has no solution");
}
private boolean isSorted(int[] numbers){
for(int i = 1 ; i < numbers.length ; i ++)
if(numbers[i] < numbers[i-1])
return false;
return true;
}
private static void printArr(int[] nums){
for(int num: nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
printArr((new Solution3()).twoSum(nums, target));
}
}
课后作业：LeetCode 125、344、345、11
3-7 滑动窗口 Minimum Size Subarray Sum
题目：LeetCode 209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
// 209. Minimum Size Subarray Sum
// https://leetcode.com/problems/minimum-size-subarray-sum/description/
//
// 暴力解法
// 该方法在 Leetcode 中会超时！
// 时间复杂度: O(n^3)
// 空间复杂度: O(1)
public class Solution1 {
public int minSubArrayLen(int s, int[] nums) {
if(s <= 0 || nums == null)
throw new IllegalArgumentException("Illigal Arguments");
int res = nums.length + 1;
for(int l = 0 ; l < nums.length ; l ++)
for(int r = l ; r < nums.length ; r ++){
int sum = 0;
for(int i = l ; i <= r ; i ++)
sum += nums[i];
if(sum >= s)
res = Math.min(res, r - l + 1);
}
if(res == nums.length + 1)
return 0;
return res;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 2, 4, 3};
int s = 7;
System.out.println((new Solution1()).minSubArrayLen(s, nums));
}
}
// 209. Minimum Size Subarray Sum
// https://leetcode.com/problems/minimum-size-subarray-sum/description/
//
// 优化暴力解
// 时间复杂度: O(n^2)
// 空间复杂度: O(n)
public class Solution2 {
public int minSubArrayLen(int s, int[] nums) {
if(s <= 0 || nums == null)
throw new IllegalArgumentException("Illigal Arguments");
// sums[i]存放nums[0...i-1]的和
int[] sums = new int[nums.length + 1];
sums[0] = 0;
for(int i = 1 ; i <= nums.length ; i ++)
sums[i] = sums[i-1] + nums[i-1];
int res = nums.length + 1;
for(int l = 0 ; l < nums.length ; l ++)
for(int r = l ; r < nums.length ; r ++){
// 使用sums[r+1] - sums[l] 快速获得nums[l...r]的和
if(sums[r+1] - sums[l] >= s)
res = Math.min(res, r - l + 1);
}
if(res == nums.length + 1)
return 0;
return res;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 2, 4, 3};
int s = 7;
System.out.println((new Solution2()).minSubArrayLen(s, nums));
}
}
// 209. Minimum Size Subarray Sum
// https://leetcode.com/problems/minimum-size-subarray-sum/description/
//
// 滑动窗口的思路
// 时间复杂度: O(n)
// 空间复杂度: O(1)
public class Solution3 {
public int minSubArrayLen(int s, int[] nums) {
if(s <= 0 || nums == null)
throw new IllegalArgumentException("Illigal Arguments");
int l = 0 , r = -1; // nums[l...r]为我们的滑动窗口
int sum = 0;
int res = nums.length + 1;
while(l < nums.length){ // 窗口的左边界在数组范围内,则循环继续
if(r + 1 < nums.length && sum < s)
sum += nums[++r];
else // r已经到头 或者 sum >= s
sum -= nums[l++];
if(sum >= s)
res = Math.min(res, r - l + 1);
}
if(res == nums.length + 1)
return 0;
return res;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 2, 4, 3};
int s = 7;
System.out.println((new Solution3()).minSubArrayLen(s, nums));
}
}
// 209. Minimum Size Subarray Sum// https://leetcode.com/problems/minimum-size-subarray-sum/description///// 另外一个滑动窗口的实现, 仅供参考// 时间复杂度: O(n)// 空间复杂度: O(1)public class Solution4 { public int minSubArrayLen(int s, int[] nums) { if(s <= 0 || nums == null) throw new IllegalArgumentException("Illigal Arguments"); int l = 0 , r = -1; // [l...r]为我们的窗口 int sum = 0; int res = nums.length + 1; while(r + 1 < nums.length){ // 窗口的右边界无法继续扩展了, 则循环继续 while(r + 1 < nums.length && sum < s)