Java算法OJ(13)双指针

news/2025/3/29 1:41:22/


目录

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/

方法一:

java">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);}}

代码分析

  1. happy 方法

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

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

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

    • 循环直到 n 变为 0,最后返回 res

  2. isHappy 方法

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

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

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

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

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

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

核心思路总结

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

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

  • 终止条件:如果平方和最终为 1,则该数是快乐数。


 方法二:

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

 代码分析

  1. bitSquareSum 方法

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

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

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

    • 循环直到 n 变为 0,最后返回 sum

  2. isHappy 方法

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

    • 使用快慢指针的思想:

      • slow 和 fast 初始都指向 n

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

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

    • 如果 slow 和 fast 相遇(即 slow == fast),说明存在循环。

    • 如果相遇时的值为 1,说明是快乐数;否则,不是快乐数。


核心思路总结

  1. 计算平方和

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

  2. 快慢指针检测循环

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

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

    • 如果相遇时的值为 1,说明是快乐数;否则,不是快乐数。

  3. 空间优化

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

2.2盛最多水的容器

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

方法一:

java">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);}

代码分析

  1. area 方法

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

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

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

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

    • 返回计算得到的面积。

  2. maxArea 方法

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

    • 使用双指针的方法:

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

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

    • 在 while 循环中:

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

      • 移动指针:

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

        • 否则,移动左指针 i++(因为右边的线可能更高,可以尝试找到更高的线)。

    • 当 i == j 时,循环结束,返回 area


核心思路总结

  1. 双指针法

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

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

  2. 面积计算

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

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

  3. 指针移动策略

    • 每次移动高度较小的指针,因为移动高度较大的指针不会增加面积(面积受限于较小的高度)。

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


 方法二:

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

代码分析

  1. 初始化

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

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

  2. 双指针循环

    • 在 while 循环中,当 i < j 时,执行以下操作:

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

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

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

        • 移动左指针 i++(因为左边的线较短,移动右指针不会增加面积)。

      • 否则:

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

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

        • 移动右指针 j--(因为右边的线较短,移动左指针不会增加面积)。

  3. 返回结果

    • 当 i >= j 时,循环结束,返回 res


核心思路总结

  1. 双指针法

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

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

  2. 面积计算

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

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

  3. 指针移动策略

    • 每次移动高度较小的指针,因为移动高度较大的指针不会增加面积(面积受限于较小的高度)。

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

2.3有效的三角形的个数

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

方法一:

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

代码分析

  1. 排序

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

  2. 双重循环

    • 使用双重循环遍历数组:

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

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

  3. 二分查找

    • 对于固定的 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 记录的是满足条件的最大下标。

  4. 统计有效三元组

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

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

  5. 返回结果

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


核心思路总结

  1. 排序

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

  2. 双重循环 + 二分查找

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

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

  3. 三角形判定条件

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

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

  4. 统计有效三元组

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


方法二:

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

代码分析

  1. 排序

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

  2. 双重循环

    • 使用双重循环遍历数组:

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

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

  3. 双指针查找

    • 对于固定的 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 个有效的三元组。

  4. 统计有效三元组

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

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

  5. 返回结果

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


核心思路总结

  1. 排序

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

  2. 双重循环 + 双指针

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

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

  3. 三角形判定条件

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

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

  4. 统计有效三元组

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

2.4和为s的两个数

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

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

 代码分析

  1. 初始化

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

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

  2. 双指针查找

    • 在 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++(因为数组是有序的,左边的数较小,移动左指针可以增大和)。

  3. 返回结果

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

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


核心思路总结

  1. 双指针法

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

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

  2. 数组有序性

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

    • 如果和大于 sum,移动右指针;如果和小于 sum,移动左指针。

  3. 返回结果

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

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

2.5三数之和

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

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

 代码分析

  1. 排序

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

  2. 外层循环

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

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

  3. 双指针查找

    • 对于固定的 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--(因为数组是有序的,右边的数较大,移动右指针可以减小和)。

  4. 返回结果

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


核心思路总结

  1. 排序

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

  2. 外层循环 + 双指针

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

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

  3. 跳过重复元素

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

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

  4. 结果存储

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

2.6四数之和

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

 

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

 代码分析

  1. 排序

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

  2. 双重循环

    • 使用双重循环遍历数组:

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

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

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

  3. 双指针查找

    • 对于固定的 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--(因为数组是有序的,右边的数较大,移动右指针可以减小和)。

  4. 返回结果

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


核心思路总结

  1. 排序

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

  2. 双重循环 + 双指针

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

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

  3. 跳过重复元素

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

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

  4. 结果存储

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

3.小结

今天的分享到这里就结束了,喜欢的小伙伴点点赞点点关注,你的支持就是对我最大的鼓励,大家加油!


http://www.ppmy.cn/news/1582901.html

相关文章

Java高频面试之集合-15

hello啊&#xff0c;各位观众姥爷们&#xff01;&#xff01;&#xff01;本baby今天来报道了&#xff01;哈哈哈哈哈嗝&#x1f436; 面试官&#xff1a;解决哈希冲突有哪些方法&#xff1f; 1. 开放寻址法&#xff08;Open Addressing&#xff09; 核心思想&#xff1a;当哈…

MD2Card(markdown)

MD2Card 介绍&#xff1a; 1.小红书爆款神器&#xff0c;Markdown笔记秒转高颜值卡片 2.实时预览15种主题&#xff0c;自动拆长文&#xff0c;图片/SVG导出即用 3.零门槛不登录&#xff0c;免费无限生成&#xff0c;专治排版废和设计手残党 网站地址&#xff1a; https://md2…

MyBatis-Flex、MyBatis-Plus 与 Fluent-Mybatis 的比较分析

MyBatis-Flex、MyBatis-Plus 与 Fluent-Mybatis 的比较分析 在日常开发中&#xff0c;很多项目会选择 MyBatis 作为 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;而为了减少样板代码和提升开发效率&#xff0c;各种扩展库层出不穷。其中&#xff0c;MyBatis-Flex…

排序复习_代码纯享

头文件 #pragma once #include<iostream> #include<vector> #include<utility> using std::vector; using std::cout; using std::cin; using std::endl; using std::swap;//插入排序 //1、直接插入排序&#xff08;稳定&#xff09; void InsertSort(vecto…

【Git学习笔记】深度理解Git的分布式版本控制系统及其管理

【Git学习笔记】深度理解Git的分布式版本控制系统及其管理 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;Git学习笔记 文章目录 【Git学习笔记】深度理解Git的分布式版本控制系统及其管理前言一. 远程操作1.1 理解分布式版本控制系统 二.远…

spring 核心注解整理

总结一下&#xff0c;核心注解涵盖以下方面&#xff1a; 依赖注入相关注解Bean定义和组件扫描注解配置类相关注解条件化配置注解作用域和生命周期注解AOP相关注解事务管理注解属性注入相关注解测试相关注解Spring Boot核心注解&#xff08;如果需要&#xff09; 每个部分列出…

深度拆解:AI Agent发展演练·数字挑战

前引&#xff1a;“Agent”从英语翻译过来就是代理、中介的意思&#xff0c;它描述了一种拥有欲望、信念、意图以及采取行动能力的载体。在计算机科学与人工智能领域中&#xff0c;“Agent”又是如何的呢&#xff1f;下面跟着我一起来看看吧&#xff01; 目录 AI Agent的发展…

修形还是需要再研究一下

最近有不少小伙伴问到修形和蜗杆砂轮的问题&#xff0c;之前虽然研究过一段时间&#xff0c;但是由于时间问题放下了&#xff0c;最近想再捡起来。 之前计算的砂轮齿形是一整段的&#xff0c;但是似乎这种对于有些小伙伴来说不太容易接受&#xff0c;希望按照修形的区域进行分…