数据结构与算法 - 双指针

一、移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]输出: [0]

提示:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

进阶：你能尽量减少完成的操作次数吗？

解法一：双指针法

在循环中，右指针right向右移动，如果当前元素不为0，则将其与左指针指向的元素交换，并且左指针向右移动。 

class Solution {public void moveZeroes(int[] nums) {int i = 0, j = 0;while(j < nums.length) {if(nums[j] != 0) {// 如果当前元素不为0，则将其与左指针指向的元素交换，并且左指针向右移动int t = nums[i];nums[i] = nums[j];nums[j] = t;i++;}j++;}}
}

二、两数之和Ⅱ - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

解法一：双指针法。执行耗时1ms

class Solution {public int[] twoSum(int[] numbers, int target) {int i = 0, j = numbers.length - 1;while (i < j) {int sum = numbers[i] + numbers[j];if (sum == target) {return new int[] { i + 1, j + 1 };} else if (sum < target) {i++;} else {j--;}}return new int[] {};}
}

三、三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

解法一：由三数之和转变为两数之和

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {// 跳过重复元素if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 变为两数之和int target = -nums[i];int left = i + 1;int right = nums.length - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum < target) {left++;} else if (sum > target) {right--;} else {List<Integer> triplet = new ArrayList<>();triplet.add(nums[i]);triplet.add(nums[left]);triplet.add(nums[right]);result.add(triplet);// 跳过重复的元素while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;}}}return result;}
}

或：

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> result = new LinkedList<>();dfs(3, 0, nums.length - 1, 0, nums,new LinkedList<>(), result);return result;}static void dfs(int n, int i, int j, int target, int[] nums,LinkedList<Integer> stack,List<List<Integer>> result) {if (n == 2) {// 套用两数之和求解twoSum(i, j, nums, target, stack, result);return;}for (int k = i; k < j - (n - 2); k++) {// 检查重复if (k > i && nums[k] == nums[k - 1]) {continue;}// 固定一个数字，再尝试 n-1 数字之和stack.push(nums[k]);dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result);stack.pop();}}static int count;static public void twoSum(int i, int j, int[] numbers, int target,LinkedList<Integer> stack,List<List<Integer>> result) {count++;while (i < j) {int sum = numbers[i] + numbers[j];if (sum < target) {i++;} else if (sum > target) {j--;} else { // 找到解ArrayList<Integer> list = new ArrayList<>(stack);list.add(numbers[i]);list.add(numbers[j]);result.add(list);// 继续查找其它的解i++;j--;while (i < j && numbers[i] == numbers[i - 1]) {i++;}while (i < j && numbers[j] == numbers[j + 1]) {j--;}}}}
}

四、四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

解法一：双指针法

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result = new ArrayList<>();int n = nums.length;if (n < 4) {return result;}Arrays.sort(nums);for (int i = 0; i < n - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {// 处理重复元素continue;}for (int j = i + 1; j < n - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}int left = j + 1;int right = n - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum < target) {left++;} else if (sum > target) {right--;} else {List<Integer> quadruplet = new ArrayList<>();quadruplet.add(nums[i]);quadruplet.add(nums[j]);quadruplet.add(nums[left]);quadruplet.add(nums[right]);result.add(quadruplet);// 处理重复元素while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;}}}}return result;}
}

五、盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

解法一：双指针法

class Solution {public int maxArea(int[] height) {int left = 0, right = height.length - 1;int result = 0;while (left < right) {result = Math.max(result, (right - left) * Math.min(height[left], height[right]));if (height[left] > height[right]) {--right;} else {++left;}}return result;}
}

六、反转字符数组

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

• 1 <= s.length <= 10^5
• s[i] 都是 ASCII 码表中的可打印字符

解法一：双指针法

class Solution {public void reverseString(char[] s) {int i = 0, j = s.length - 1;while (i < j) {swap(s, i, j);i++;j--;}}private void swap(char[] s, int i, int j) {char t = s[i];s[i] = s[j];s[j] = t;}
}

七、反转字符串Ⅱ

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

提示：

• 1 <= s.length <= 10^4
• s 仅由小写英文组成
• 1 <= k <= 10^4

解法一：双指针法

class Solution {public String reverseStr(String s, int k) {int n = s.length();char[] chars = s.toCharArray();for (int i = 0; i < n; i += 2 * k) {// 只反转前k个字符int start = i;int end = Math.min(i + k - 1, n - 1);while (start < end) {swap(chars, start, end);start++;end--;}}return new String(chars);}private void swap(char[] s, int i, int j) {char t = s[i];s[i] = s[j];s[j] = t;}
}