java-leetcode面试题解双指针之第18题四数之和.zip资源-CSDN下载

共1个文件

java：1个

需积分: 50 147 浏览量 2024-03-25 05:34:02 上传评论收藏 2KB ZIP 举报

在Java编程领域，LeetCode是一个非常受欢迎的在线平台，它提供了大量的编程题目，帮助开发者提升算法能力和解决问题的技巧。在面试准备过程中，LeetCode题目常常作为考察候选人技术能力的重要手段。其中，第18题“四数之和”是双指针技术的一个经典应用，这道题目的目标是在一个整数数组中找到所有和为特定值的四个数的组合。题目描述如下：给定一个包含n个整数的数组nums和一个目标值target，找出nums中的四个整数，使得它们的和等于target。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。双指针是一种常用的解决数组问题的策略，通常用于排序或近似排序的数组。在这道题中，我们可以首先对数组进行排序，然后使用两个指针，一个从数组的开头开始（low），另一个从数组的末尾开始（high）。我们不断调整这两个指针，直到找到满足条件的四数之和或者确定不存在这样的组合。以下是使用双指针求解该问题的基本步骤： 1. **预处理**：对输入数组nums进行排序。可以使用Java内置的`Arrays.sort()`方法。 2. **初始化指针**：设置两个指针low和high，low指向数组的第一个元素，high指向数组的最后一个元素。 3. **主循环**：在满足low < high的条件下执行以下操作： - 计算当前四个数的和：`sum = nums[low] + nums[low+1] + nums[high-1] + nums[high]`。 - 检查sum是否等于目标值target： - 如果sum等于target，说明找到了一组解，将其添加到结果集中，然后将low指针向右移动一位（避免重复元素），high指针向左移动一位，继续寻找其他可能的组合。 - 如果sum小于target，说明需要增加数组中较小的元素的和，因此将low指针向右移动一位。 - 如果sum大于target，说明需要减小数组中较大的元素的和，因此将high指针向左移动一位。 4. **返回结果**：返回所有找到的组合。这个算法的时间复杂度是O(n^2)，其中n是数组的长度，因为我们需要对数组进行排序，然后用双指针遍历一次数组。空间复杂度是O(1)，因为我们没有使用额外的空间来存储数据，只使用了几个变量。在实际编程中，为了提高代码的可读性和复用性，我们可以封装这个解题逻辑到一个单独的方法中，并且考虑边界条件和异常处理，如数组为空、元素数量不足四等。通过解决LeetCode的这类题目，开发者不仅可以熟练掌握双指针技巧，还能锻炼对数组操作、排序算法以及条件判断的理解，这对于提高Java编程能力，尤其是面试表现，具有显著的帮助。

资源推荐

资源详情

资源评论

收起资源包目录

java_leetcode面试题解双指针之第18题四数之和.zip （1个子文件）

java_leetcode面试题解双指针之第18题四数之和

0018-4sum

src

Solution.java 2KB

import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { // 方法：三数之和的推广，理解这道题需要先做「力扣」第 15 题：三数之和 // 时间复杂度：O(n^3); // 空间复杂度：O(n); public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> res = new ArrayList<>(); int len = nums.length; if (len < 4) { return res; } Arrays.sort(nums); // len-4 len-3 len-2 len-1 for (int i = 0; i < len - 3; i++) { // 跳过重复的解 1（以排序为前提） if (i > 0 && nums[i] == nums[i - 1]) { continue; } // len-3 len-2 len-1 for (int j = i + 1; j < len - 2; j++) { // 跳过重复的解 2（以排序为前提） if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } // 接下来使用双指针 int left = j + 1; int right = len - 1; while (left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { List<Integer> oneSolution = new ArrayList<>(); oneSolution.add(nums[i]); oneSolution.add(nums[j]); oneSolution.add(nums[left]); oneSolution.add(nums[right]); res.add(oneSolution); // 跳过重复的解 3（以排序为前提） while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right] == nums[right - 1]) { right--; } // 这一步不要忘记了 left++; right--; } else if (sum < target) { left++; } else { right--; } } } } return res; } }

评论收藏

内容反馈