LeetCode数组题分析与解法（2）

我不是女神ヾ 2023-10-05 12:47 52阅读 0赞

LeetCode上数组题的分析与解法的第二部分。这些题目都是通过两个指针来完成。

### 翻转字符串 （\#1183） ###

翻转字符串是经典的算法问题了。可以通过两个指针来完成，分别从字符串的首尾开始遍历。

public void reverseString(char[] s) {  if (s.length <= 1) {    return;  }  for (int i = 0, j = s.length - 1; i < j; i++, j--) {    char temp = s[j];    s[j] = s[i];    s[i] = temp;  }}

### 数组划分1 （\#1154） ###

数组中包含了`2n`个整数。对这些整数进行分组，每组中有2个元素。要求每个分组中最小值的和尽可能大。返回这些最小值的和的最大值。比如，数组`[1, 4, 2, 3]`分成两组，`[1, 2]`和`[3, 4]`。这两组的最小值分别是`1`和`3`，得到的和是`4`。

这道题目的解法是先对数组进行排序，然后按照从小到大的顺序分组即可。这样得到的分组满足题目所要求的条件。

public int arrayPairSum(int[] nums) {  Arrays.sort(nums);  int sum = 0;  for (int i = 0; i < nums.length; i+=2) {    sum += nums[i];  }  return sum;}

可以简单的证明一下这样的算法是正确的。对于排序之后的分组，如果找出来两个分组，将其中的任意两个元素交换位置。交换之后所得到的新分组的最小值的和，必然小于之前的分组方式。因为在交换之后，之前数值较小的那个分组的最小值保持不变，仍然为四个元素中的最小值；而之前数值较大的那个分组的最小值变小了，最小值变成了交换过来的较小的值。比如，`a`、`b`、`c`和`d`四个元素，满足`a <= b <= c <= d`。之前的分组方式为`(a, b)`和`(c, d)`，两个分组的最小值的和为`a + c`。任意交换两个元素之后，假设得到分组`(a, c)`和`(b, d)`，最小值的和变为`a + b`。显然`a + b <= a + c`。通过反证法就证明了算法的正确性。

### 删除元素 （\#1151） ###

给定一个数组`nums`和值`val`，从数组中删除值为`val`的元素，并返回删除后新的数组长度。要求在原始数组上直接进行修改。

解法是用快和慢两个指针。快指针用来遍历数组，慢指针用来修改数组中的值来删除元素。

public int removeElement(int[] nums, int val) {  int i = 0;  for (int j = 0; j < nums.length; j++) {    if (nums[j] != val) {      nums[i++] = nums[j];    }  }  return i;}

### 移动0 （\#1174） ###

给定一个数组`nums`，把其中的`0`都移动到数组末尾，并保持其他非`0`元素的相对顺序。

这也是一个典型的双指针的问题，和删除元素（\#1151）的解法类似，先把非`0`的元素移动到数组前部，然后把剩下的元素设为`0`即可。

public void moveZeroes(int[] nums) {  int i = 0;  for (int j = 0; j < nums.length; j++) {    if (nums[j] != 0) {      nums[i++] = nums[j];    }  }  if (i < nums.length) {    Arrays.fill(nums, i, nums.length, 0);  }}

另外一种解法是不需要后续的把数组末尾设置为`0`的操作，而是在遍历时直接设置。

public void moveZeroes(int[] nums) {  int i = 0;  for (int j = 0; j < nums.length; j++) {    if (nums[j] != 0) {      nums[i] = nums[j];      if (i != j) nums[j] = 0;      i++;    }  }}

### 从已排序数组中删除重复元素 （\#1173） ###

从一个已排序数组`nums`中删除重复元素并返回新的长度。

使用快和慢两个指针。慢指针指向当前需要检查重复的元素，快指针遍历扫描，直到找到第一个不相同的元素。这个元素被放置在慢指针当前元素的下一个位置，然后继续遍历。

public int removeDuplicates(int[] nums) {  if (nums.length == 0) return 0;  int i = 0;  for (int j = 1; j < nums.length; j++) {    if (nums[j] != nums[i]) {      nums[++i] = nums[j];    }  }  return i + 1;}

### 最多的连续1 （\#1301） ###

给定一个只包含`0`和`1`的数组，找出来其中包含的连续`1`的最大个数。比如，`[1, 1, 0, 1, 1, 1]`中连续`1`的最大个数是`3`。

解法同样是使用快和慢两个指针。快指针遍历数组，慢指针指向的是`1`之前的最后一个`0`。需要额外处理的情况是数组的最后一个元素为`1`的情况。

public int findMaxConsecutiveOnes(int[] nums) {  int max = 0;  int i = -1;  for (int j = 0; j < nums.length; j++) {    if (nums[j] == 0) {      max = Math.max(max, j - i - 1);      i = j;    } else if (j == nums.length - 1) {      max = Math.max(max, j - i);    }  }  return max;}

### 子数组和的最小长度 （\#1299） ###

给定一个只包含`n`个正整数的数组和正整数`s`，找到长度最小的连续子数组使得其和大于或等于`s`。比如，数组`[2, 3, 1, 2, 4, 3]`和值`7`，对应的结果为`2`，由子数组`[4, 3]`来满足。

解法是使用两个指针。慢指针指向当前检查的子数组的左边界，快指针指向右边界。当子数组的和大于或等于`s`时，得到一个可能的解。这个时候，需要移动慢指针来缩小子数组以求得可能的更优的解。

public int minSubArrayLen(int s, int[] nums) {  int minLength = Integer.MAX_VALUE;  int sum = 0;  int left = 0;  for (int i = 0; i < nums.length; i++) {    sum += nums[i];    while (sum >= s) {      minLength = Math.min(minLength, i + 1 - left);      sum -= nums[left++];    }  }  return minLength != Integer.MAX_VALUE ? minLength : 0;}

### 两个数的和 - 数组有序 （\#1153） ###

对于一个升序排列的数组和给定的和，找出数组中的两个元素，使得它们的和等于给定值。

解法是使用左和右两个指针，分别从数组的两头遍历。因为数组有序，如果当前的和大于给定值，移动右边指针；反之则移动左边指针。

public int[] twoSum(int[] numbers, int target) {  int[] result = new int[2];  if (numbers == null || numbers.length < 2) {    return result;  }  int left = 0, right = numbers.length - 1;  while (left < right){    int sum = numbers[left] + numbers[right];    if (sum == target) {      result[0] = left + 1;      result[1] = right + 1;      break;    } else if (sum > target) {      right--;    } else {      left++;    }  }  return result;}