Java算法OJ（13）双指针

1.前言

2.正文

2.1快乐数

2.2盛最多水的容器

2.3有效的三角形的个数

2.4和为s的两个数

2.5三数之和

2.6四数之和

3.小结

1.前言

哈喽大家好吖，今天继续加练算法题目，一共六道双指针，希望能对大家有所帮助，废话不多说让我们开始吧。

2.正文

2.1快乐数

202. 快乐数 - 力扣（LeetCode）https://leetcode.cn/problems/happy-number/description/

方法一：

public int happy(int n){int res = 0;while(n != 0){res += (n % 10) * (n % 10);n /= 10;}return res;}public boolean isHappy(int n) {HashSet <Integer> set = new HashSet<>();int ans = n;while(true){ans = happy(ans);if(ans == 1){return true;}if(set.contains(ans)){return false;}set.add(ans);}}

代码分析

happy 方法：

该方法的作用是计算一个整数 n 的每个数字的平方和。

通过 n % 10 获取 n 的最后一位数字，然后将其平方并累加到 res 中。

通过 n /= 10 去掉 n 的最后一位数字。

循环直到 n 变为 0，最后返回 res。

isHappy 方法：

该方法用于判断一个整数 n 是否为快乐数。

使用一个 HashSet 来记录已经出现过的数字，用于检测是否进入了循环。

通过 happy 方法计算 n 的平方和，并将结果存储在 ans 中。

如果 ans 等于 1，说明 n 是快乐数，返回 true。

如果 ans 已经存在于 HashSet 中，说明进入了循环，返回 false。

否则，将 ans 添加到 HashSet 中，并继续循环。

核心思路总结

计算平方和：通过 happy 方法计算一个数的每个数字的平方和。

检测循环：通过 HashSet 记录已经出现过的数字，如果某个数字重复出现，说明进入了循环，该数不是快乐数。

终止条件：如果平方和最终为 1，则该数是快乐数。

方法二：

public int bitSquareSum(int n) {int sum = 0;while(n > 0){int bit = n % 10;sum += bit * bit;n = n / 10;}return sum;}public boolean isHappy(int n) {int slow = n, fast = n;do{slow = bitSquareSum(slow);fast = bitSquareSum(fast);fast = bitSquareSum(fast);}while(slow != fast);return slow == 1;}

代码分析

bitSquareSum 方法：

该方法的作用是计算一个整数 n 的每个数字的平方和。

通过 n % 10 获取 n 的最后一位数字，然后将其平方并累加到 sum 中。

通过 n /= 10 去掉 n 的最后一位数字。

循环直到 n 变为 0，最后返回 sum。

isHappy 方法：

该方法用于判断一个整数 n 是否为快乐数。

使用快慢指针的思想：

slow 和 fast 初始都指向 n。

slow 每次调用一次 bitSquareSum，相当于每次走一步。

fast 每次调用两次 bitSquareSum，相当于每次走两步。

如果 slow 和 fast 相遇（即 slow == fast），说明存在循环。

如果相遇时的值为 1，说明是快乐数；否则，不是快乐数。

核心思路总结

计算平方和：

通过 bitSquareSum 方法计算一个数的每个数字的平方和。

快慢指针检测循环：

使用快慢指针的思想来检测是否进入了循环。

如果快慢指针相遇，说明存在循环。

如果相遇时的值为 1，说明是快乐数；否则，不是快乐数。

空间优化：

相比于使用 HashSet 的方法，快慢指针方法不需要额外的空间，空间复杂度为 O(1)。

2.2盛最多水的容器

11. 盛最多水的容器 - 力扣（LeetCode）https://leetcode.cn/problems/container-with-most-water/description/

方法一：

public int maxArea(int[] height) {int i = 0,j = height.length - 1;int area = 0;while(i != j){area = Math.max(area(i,j,height),area);if((height[j] - height[i]) <= 0)j--;else i++;}return area;}public int area(int a,int b,int[] height){return Math.min(height[a],height[b]) * Math.abs(b - a);}

代码分析

area 方法：

该方法的作用是计算两条线之间的容器的面积。

面积的计算公式为：面积 = 两条线的最小高度 * 两条线之间的距离。

使用 Math.min(height[a], height[b]) 获取两条线的最小高度。

使用 Math.abs(b - a) 获取两条线之间的距离。

返回计算得到的面积。

maxArea 方法：

该方法用于找到可以容纳最多水的容器。

使用双指针的方法：

初始化两个指针 i 和 j，分别指向数组的起始位置和末尾位置。

初始化 area 为 0，用于记录当前的最大面积。

在 while 循环中：

计算当前指针 i 和 j 之间的面积，并更新 area 为当前面积和历史最大面积中的较大值。

移动指针：

如果 height[j] <= height[i]，则移动右指针 j--（因为左边的线可能更高，可以尝试找到更高的线）。

否则，移动左指针 i++（因为右边的线可能更高，可以尝试找到更高的线）。

当 i == j 时，循环结束，返回 area。

核心思路总结

双指针法：

使用两个指针 i 和 j，分别指向数组的起始位置和末尾位置。

通过移动指针来缩小搜索范围，同时计算当前指针之间的面积。

面积计算：

容器的面积由两条线的最小高度和它们之间的距离决定。

面积公式：面积 = min(height[i], height[j]) * (j - i)。

指针移动策略：

每次移动高度较小的指针，因为移动高度较大的指针不会增加面积（面积受限于较小的高度）。

通过这种方式，可以逐步缩小搜索范围，同时确保不会错过最大面积。

方法二：

public int maxArea(int[] height) {int i = 0, j = height.length - 1, res = 0;while(i < j) {res = height[i] < height[j] ?Math.max(res, (j - i) * height[i++]):Math.max(res, (j - i) * height[j--]);}return res;}

代码分析

初始化：

使用两个指针 i 和 j，分别指向数组的起始位置和末尾位置。

初始化 res 为 0，用于记录当前的最大面积。

双指针循环：

在 while 循环中，当 i < j 时，执行以下操作：

如果 height[i] < height[j]：

计算当前指针 i 和 j 之间的面积：(j - i) * height[i]。

更新 res 为当前面积和历史最大面积中的较大值。

移动左指针 i++（因为左边的线较短，移动右指针不会增加面积）。

否则：

计算当前指针 i 和 j 之间的面积：(j - i) * height[j]。

更新 res 为当前面积和历史最大面积中的较大值。

移动右指针 j--（因为右边的线较短，移动左指针不会增加面积）。

返回结果：

当 i >= j 时，循环结束，返回 res。

核心思路总结

双指针法：

使用两个指针 i 和 j，分别指向数组的起始位置和末尾位置。

通过移动指针来缩小搜索范围，同时计算当前指针之间的面积。

面积计算：

容器的面积由两条线的最小高度和它们之间的距离决定。

面积公式：面积 = min(height[i], height[j]) * (j - i)。

指针移动策略：

每次移动高度较小的指针，因为移动高度较大的指针不会增加面积（面积受限于较小的高度）。

通过这种方式，可以逐步缩小搜索范围，同时确保不会错过最大面积。

2.3有效的三角形的个数

611. 有效三角形的个数 - 力扣（LeetCode）https://leetcode.cn/problems/valid-triangle-number/description/

方法一：

public int triangleNumber(int[] nums) {int ans = 0;Arrays.sort(nums);for(int i = 0;i < nums.length;i++){for(int j = i + 1;j < nums.length;j++){int left = j + 1,right = nums.length - 1,k = j;while (left <= right) {int mid = (left + right)/2;if(nums[i] + nums[j] > nums[mid]){k = mid;left = mid + 1;}else{right = mid - 1;}}ans += k - j;}}return ans;}

代码分析

排序：

首先对数组 nums 进行升序排序。排序的目的是为了方便后续使用双指针或二分查找来优化查找过程。

双重循环：

使用双重循环遍历数组：

外层循环固定一个数 nums[i]，作为三角形的第一条边。

内层循环固定第二个数 nums[j]，作为三角形的第二条边。

二分查找：

对于固定的 nums[i] 和 nums[j]，使用二分查找来确定满足 nums[i] + nums[j] > nums[k] 的最大 k。

初始化 left = j + 1 和 right = nums.length - 1，表示搜索范围。

在 while 循环中：

计算中间位置 mid = (left + right) / 2。

如果 nums[i] + nums[j] > nums[mid]，说明 mid 满足条件，尝试向右扩展范围（left = mid + 1）。

否则，向左缩小范围（right = mid - 1）。

最终，k 记录的是满足条件的最大下标。

统计有效三元组：

对于固定的 nums[i] 和 nums[j]，满足条件的 k 的范围是 [j + 1, k]，共有 k - j 个有效的三元组。

将 k - j 累加到结果 ans 中。

返回结果：

最终返回 ans，即所有有效三元组的个数。

核心思路总结

排序：

对数组进行排序，使得后续的查找过程更加高效。

双重循环 + 二分查找：

外层循环固定第一条边，内层循环固定第二条边。

对于固定的两条边，使用二分查找确定满足条件的第三条边的最大下标。

三角形判定条件：

对于排序后的数组，如果 nums[i] + nums[j] > nums[k]，则 nums[i] + nums[k] > nums[j] 和 nums[j] + nums[k] > nums[i] 也一定成立（因为数组已排序）。

因此，只需要检查 nums[i] + nums[j] > nums[k] 即可。

统计有效三元组：

对于固定的 nums[i] 和 nums[j]，满足条件的 k 的范围是 [j + 1, k]，共有 k - j 个有效的三元组。

方法二：

public int triangleNumber(int[] nums) {int ans = 0;Arrays.sort(nums);for(int i = 0;i < nums.length;i++){int k = i + 1;for(int j = i + 1;j <nums.length;j++){while(k + 1 < nums.length && nums[k + 1] < nums[i] + nums[j]){k++;}ans += Math.max(k - j,0);}}return ans;}

代码分析

排序：

首先对数组 nums 进行升序排序。排序的目的是为了方便后续使用双指针来优化查找过程。

双重循环：

使用双重循环遍历数组：

外层循环固定一个数 nums[i]，作为三角形的第一条边。

内层循环固定第二个数 nums[j]，作为三角形的第二条边。

双指针查找：

对于固定的 nums[i] 和 nums[j]，使用双指针的方法来确定满足 nums[i] + nums[j] > nums[k] 的最大 k。

初始化 k = i + 1，表示第三条边的起始位置。

在 while 循环中：

如果 k + 1 < nums.length 且 nums[k + 1] < nums[i] + nums[j]，则移动右指针 k++。

这样，k 会指向满足条件的最大下标。

最终，满足条件的 k 的范围是 [j + 1, k]，共有 k - j 个有效的三元组。

统计有效三元组：

对于固定的 nums[i] 和 nums[j]，满足条件的 k 的范围是 [j + 1, k]，共有 k - j 个有效的三元组。

将 k - j 累加到结果 ans 中。

返回结果：

最终返回 ans，即所有有效三元组的个数。

核心思路总结

排序：

对数组进行排序，使得后续的查找过程更加高效。

双重循环 + 双指针：

外层循环固定第一条边，内层循环固定第二条边。

对于固定的两条边，使用双指针确定满足条件的第三条边的最大下标。

三角形判定条件：

对于排序后的数组，如果 nums[i] + nums[j] > nums[k]，则 nums[i] + nums[k] > nums[j] 和 nums[j] + nums[k] > nums[i] 也一定成立（因为数组已排序）。

因此，只需要检查 nums[i] + nums[j] > nums[k] 即可。

统计有效三元组：

对于固定的 nums[i] 和 nums[j]，满足条件的 k 的范围是 [j + 1, k]，共有 k - j 个有效的三元组。

2.4和为s的两个数

和为S的两个数字__牛客网和为S的两个数字 ,“一战通offer”互联网实习季编程挑战模拟卷 https://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {ArrayList<Integer> ans = new ArrayList<>();int i = 0,j = array.length - 1;while(i < j){if(array[i] + array[j] == sum){ans.add(array[i]);ans.add(array[j]);return ans;}else if(array[i] + array[j] > sum){j--;}else if(array[i] + array[j] < sum){i++;}}return ans;}

代码分析

初始化：

使用一个 ArrayList<Integer> 来存储结果。

使用两个指针 i 和 j，分别指向数组的起始位置和末尾位置。

双指针查找：

在 while 循环中，当 i < j 时，执行以下操作：

如果 array[i] + array[j] == sum：

将 array[i] 和 array[j] 添加到结果列表 ans 中。

返回结果列表 ans。

如果 array[i] + array[j] > sum：

移动右指针 j--（因为数组是有序的，右边的数较大，移动右指针可以减小和）。

如果 array[i] + array[j] < sum：

移动左指针 i++（因为数组是有序的，左边的数较小，移动左指针可以增大和）。

返回结果：

如果找到满足条件的两个数，直接返回结果列表。

如果循环结束后仍未找到满足条件的两个数，返回空的 ans。

核心思路总结

双指针法：

使用两个指针 i 和 j，分别指向数组的起始位置和末尾位置。

通过移动指针来缩小搜索范围，同时计算当前指针指向的两个数的和。

数组有序性：

数组是有序的，因此可以通过比较 array[i] + array[j] 与 sum 的大小关系来决定移动哪个指针。

如果和大于 sum，移动右指针；如果和小于 sum，移动左指针。

返回结果：

如果找到满足条件的两个数，直接返回结果。

如果未找到满足条件的两个数，返回空列表。

2.5三数之和

15. 三数之和 - 力扣（LeetCode）https://leetcode.cn/problems/3sum/description/

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<>();Arrays.sort(nums);int n = nums.length;for(int i = 0;i < n;i++){if(i > 0 && nums[i - 1] == nums[i]){continue;}int left = i + 1;int right = n - 1;int target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum == target){list.add(Arrays.asList(nums[i],nums[left],nums[right]));left++;right--;while(left < right && nums[left] == nums[left - 1])left++;while(left < right && nums[right] == nums[right + 1])right--;}else if(sum < target){left++;}else{right--;}}}return list;}

代码分析

排序：

首先对数组 nums 进行升序排序。排序的目的是为了方便后续使用双指针来优化查找过程，并且可以方便地跳过重复的元素。

外层循环：

使用一个外层循环遍历数组，固定一个数 nums[i] 作为三元组的第一个数。

如果 nums[i] 与前一个数 nums[i - 1] 相同，则跳过当前循环（避免重复的三元组）。

双指针查找：

对于固定的 nums[i]，使用双指针的方法在剩余的子数组中查找两个数 nums[left] 和 nums[right]，使得 nums[i] + nums[left] + nums[right] = 0。

初始化 left = i + 1 和 right = n - 1，表示搜索范围。

在 while 循环中：

计算当前的和 sum = nums[left] + nums[right]。

如果 sum == target（即 sum == -nums[i]）：

将 [nums[i], nums[left], nums[right]] 添加到结果列表 list 中。

移动左指针 left++ 和右指针 right--。

跳过重复的 nums[left] 和 nums[right]，避免重复的三元组。

如果 sum < target：

移动左指针 left++（因为数组是有序的，左边的数较小，移动左指针可以增大和）。

如果 sum > target：

移动右指针 right--（因为数组是有序的，右边的数较大，移动右指针可以减小和）。

返回结果：

最终返回结果列表 list，其中包含所有满足条件的不重复三元组。

核心思路总结

排序：

对数组进行排序，使得后续的查找过程更加高效，并且可以方便地跳过重复的元素。

外层循环 + 双指针：

外层循环固定第一个数 nums[i]。

对于固定的 nums[i]，使用双指针在剩余的子数组中查找两个数 nums[left] 和 nums[right]，使得 nums[i] + nums[left] + nums[right] = 0。

跳过重复元素：

在外层循环中，如果 nums[i] 与前一个数 nums[i - 1] 相同，则跳过当前循环。

在双指针查找过程中，如果 nums[left] 或 nums[right] 与下一个数相同，则跳过重复的数。

结果存储：

将满足条件的三元组 [nums[i], nums[left], nums[right]] 添加到结果列表 list 中。

2.6四数之和

18. 四数之和 - 力扣（LeetCode）https://leetcode.cn/problems/4sum/description/

public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ans = new ArrayList<>();Arrays.sort(nums);int n = nums.length;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 l = j + 1, r = n - 1;long aim = (long) target - nums[i] - nums[j];while (l < r) {long sum = (long) nums[l] + nums[r];if (sum == aim) {ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));l++;r--;while (l < r && nums[l] == nums[l - 1]) l++;while (l < r && nums[r] == nums[r + 1]) r--;} else if (sum < aim) {l++;} else {r--;}}}}return ans;}

代码分析

排序：

首先对数组 nums 进行升序排序。排序的目的是为了方便后续使用双指针来优化查找过程，并且可以方便地跳过重复的元素。

双重循环：

使用双重循环遍历数组：

外层循环固定一个数 nums[i]，作为四元组的第一个数。

内层循环固定第二个数 nums[j]，作为四元组的第二个数。

在每次循环中，如果当前数与前一个数相同，则跳过当前循环（避免重复的四元组）。

双指针查找：

对于固定的 nums[i] 和 nums[j]，使用双指针的方法在剩余的子数组中查找两个数 nums[l] 和 nums[r]，使得 nums[i] + nums[j] + nums[l] + nums[r] = target。

初始化 l = j + 1 和 r = n - 1，表示搜索范围。

计算目标值 aim = target - nums[i] - nums[j]。

在 while 循环中：

计算当前的和 sum = nums[l] + nums[r]。

如果 sum == aim：

将 [nums[i], nums[j], nums[l], nums[r]] 添加到结果列表 ans 中。

移动左指针 l++ 和右指针 r--。

跳过重复的 nums[l] 和 nums[r]，避免重复的四元组。

如果 sum < aim：

移动左指针 l++（因为数组是有序的，左边的数较小，移动左指针可以增大和）。

如果 sum > aim：

移动右指针 r--（因为数组是有序的，右边的数较大，移动右指针可以减小和）。

返回结果：

最终返回结果列表 ans，其中包含所有满足条件的不重复四元组。

核心思路总结

排序：

对数组进行排序，使得后续的查找过程更加高效，并且可以方便地跳过重复的元素。

双重循环 + 双指针：

外层循环固定第一个数 nums[i]，内层循环固定第二个数 nums[j]。

对于固定的 nums[i] 和 nums[j]，使用双指针在剩余的子数组中查找两个数 nums[l] 和 nums[r]，使得 nums[i] + nums[j] + nums[l] + nums[r] = target。

跳过重复元素：

在外层循环和内层循环中，如果当前数与前一个数相同，则跳过当前循环。

在双指针查找过程中，如果 nums[l] 或 nums[r] 与下一个数相同，则跳过重复的数。

结果存储：

将满足条件的四元组 [nums[i], nums[j], nums[l], nums[r]] 添加到结果列表 ans 中。