如何做微信官方网站,玉环 企业网站建设,农夫山泉软文300字,想设计一个公司的网站15. 三数之和#xff0c;16. 最接近的三数之和#xff0c;17. 电话号码的字母组合#xff0c;每题做详细思路梳理#xff0c;配套PythonJava双语代码#xff0c; 2024.03.11 可通过leetcode所有测试用例。
目录
15. 三数之和
解题思路
完整代码
Java
Python
… 15. 三数之和16. 最接近的三数之和17. 电话号码的字母组合每题做详细思路梳理配套PythonJava双语代码 2024.03.11 可通过leetcode所有测试用例。
目录
15. 三数之和
解题思路
完整代码
Java
Python
编辑
16. 最接近的三数之和
解题思路
完整代码
Java
Python
17. 电话号码的字母组合
解题思路
完整代码
Java
Python 15. 三数之和 给你一个整数数组 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 。 解题思路 为了找到所有和为0且不重复的三元组我们可以使用双指针法。这个方法涉及到先对数组进行排序然后遍历数组对于每个元素使用两个指针分别指向元素之后的开始位置和数组的末尾向中间移动两个指针来找到和为0的三元组。这里有几个关键点需要注意
排序先对数组进行排序这样可以方便地跳过重复的元素。遍历从数组的开始遍历到倒数第三个元素因为我们需要的是三元组。双指针对于每个遍历到的元素将一个指针指向遍历元素的下一个位置另一个指针指向数组的末尾。根据这两个指针指向的元素之和与当前遍历到的元素之和来移动指针。跳过重复元素在遍历过程中如果遇到重复的元素需要跳过以避免重复的三元组。
完整代码
Java
public class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums); // 排序ListListInteger res new ArrayList();for (int i 0; i nums.length - 2; i) { // 遍历到倒数第三个元素if (i 0 nums[i] nums[i - 1]) { // 跳过重复元素continue;}int l i 1, r nums.length - 1;while (l r) {int sum nums[i] nums[l] nums[r];if (sum 0) {l;} else if (sum 0) {r--;} else {res.add(Arrays.asList(nums[i], nums[l], nums[r]));while (l r nums[l] nums[l 1]) l; // 跳过重复元素while (l r nums[r] nums[r - 1]) r--; // 跳过重复元素l;r--;}}}return res;}
}
Python
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:nums.sort() # 排序result []for i in range(len(nums)-2): # 遍历到倒数第三个元素if i 0 and nums[i] nums[i-1]: # 跳过重复元素continuel, r i1, len(nums)-1 # 双指针while l r:s nums[i] nums[l] nums[r]if s 0:l 1elif s 0:r - 1else:result.append([nums[i], nums[l], nums[r]])while l r and nums[l] nums[l1]: # 跳过重复元素l 1while l r and nums[r] nums[r-1]: # 跳过重复元素r - 1l 1; r - 1return result 16. 最接近的三数之和 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 示例 1 输入nums [-1,2,1,-4], target 1 输出2 解释与 target 最接近的和是 2 (-1 2 1 2) 。 示例 2 输入nums [0,0,0], target 1 输出0 提示 3 nums.length 1000 -1000 nums[i] 1000 解题思路 为了找到和与目标值 target 最接近的三个整数的和我们可以使用一种类似于解决“三数之和”问题的方法即使用双指针法。基本思路如下 排序首先对数组 nums 进行排序这有助于使用双指针法。 初始化最接近的和用一个变量记录当前找到的与 target 最接近的和初始时可以设为第一个元素、第二个元素和最后一个元素的和或者设置为一个较大的数。 遍历遍历数组对于每个元素 nums[i]使用两个指针分别指向 i 之后的元素和数组的最后一个元素。基于当前三元组的和与 target 的差距移动指针。 移动双指针如果三元组的和大于 target为了使和更接近 target应该减小和因此将右指针左移。如果三元组的和小于 target为了使和更接近 target应该增加和因此将左指针右移。 更新最接近的和在每一步中如果找到了更接近 target 的和则更新记录的最接近的和。 返回结果遍历结束后记录的最接近的和即为所求。
完整代码
Java
public class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int closestSum nums[0] nums[1] nums[nums.length - 1]; // 初始化最接近的和for (int i 0; i nums.length - 2; i) {int l i 1, r nums.length - 1;while (l r) {int currentSum nums[i] nums[l] nums[r];if (currentSum target) { // 如果等于target直接返回return currentSum;}// 更新最接近的和if (Math.abs(currentSum - target) Math.abs(closestSum - target)) {closestSum currentSum;}// 根据和与target的比较移动双指针if (currentSum target) {l;} else {r--;}}}return closestSum;}
}
Python
class Solution:def threeSumClosest(self, nums: List[int], target: int) - int:nums.sort()closest_sum sum(nums[:3]) # 初始化最接近的和for i in range(len(nums) - 2):l, r i 1, len(nums) - 1while l r:current_sum nums[i] nums[l] nums[r]if current_sum target: # 如果等于target直接返回return current_sum# 更新最接近的和if abs(current_sum - target) abs(closest_sum - target):closest_sum current_sum# 根据和与target的比较移动双指针if current_sum target:l 1else:r - 1return closest_sum
17. 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1 输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2 输入digits
输出[]示例 3 输入digits 2
输出[a,b,c]提示 0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。 解题思路 可以使用回溯法。回溯法是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解或者至少不是最后一个解回溯算法会通过在上一步进行一些变化来丢弃该解即回溯并尝试另一个可能的解。 具体到这个问题可以将每个数字对应到其可以代表的所有字母然后通过回溯遍历这些字母的所有可能组合。
创建一个映射表将每个数字映射到相应的字母。创建一个函数来实现回溯机制该函数将接受当前组合的字符串和接下来处理的数字字符串。从输入字符串的第一个数字开始将其映射到对应的所有字母并对每个字母添加到当前的组合字符串中并进行下一轮回溯即再处理下一个数字。如果数字字符串为空表示所有的数字都已处理完毕此时的组合字符串为一个完整的解将其添加到答案列表中。重复步骤3和4直到遍历完所有的数字找出所有可能的字母组合。
完整代码
Java
public class Solution {public ListString letterCombinations(String digits) {ListString combinations new ArrayList();if (digits null || digits.length() 0) {return combinations;}String[] phoneMap {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};backtrack(combinations, phoneMap, digits, 0, new StringBuilder());return combinations;}public void backtrack(ListString combinations, String[] phoneMap, String digits, int index, StringBuilder path) {if (index digits.length()) {combinations.add(path.toString());return;}String possibleLetters phoneMap[digits.charAt(index) - 0];for (char letter : possibleLetters.toCharArray()) {path.append(letter);backtrack(combinations, phoneMap, digits, index 1, path);path.deleteCharAt(path.length() - 1); // 回溯}}
}
Python
class Solution:def letterCombinations(self, digits: str) - List[str]:if not digits:return []phoneMap {2: abc, 3: def, 4: ghi, 5: jkl,6: mno, 7: pqrs, 8: tuv, 9: wxyz}def backtrack(index, path):# 如果路径长度与输入数字长度相同将其添加到结果中if len(path) len(digits):combinations.append(.join(path))return# 获取当前数字对应的所有可能的字母possible_letters phoneMap[digits[index]]for letter in possible_letters:# 添加当前字母到路径中并进入下一层回溯path.append(letter)backtrack(index 1, path)path.pop() # 回溯移除路径最后一个字母combinations []backtrack(0, [])return combinations
