16. 最接近的三数之和 3Sum Closest
给你一个长度为 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
-10^4 <= target <= 10^4
代码： 双指针
fn three_sum_closest(nums: &mut [i32], target: i32) -> i32 { nums.sort(); // 排序 let mut res = nums[0] + nums[1] + nums[2]; for i in 0..nums.len()-2 { let (mut l, mut r) = (i+1, nums.len()-1); // 双指针 while l < r { let sum = nums[i] + nums[l] + nums[r]; if (sum-target).abs() < (res-target).abs() { res = sum; } if sum == target { return target; } else if sum < target { l += 1; } else { r -= 1; } } } res } fn main() { let mut nums1 = vec![-1, 2, 1, -4]; let mut nums2 = vec![0, 0, 0]; println!("{}", three_sum_closest(&mut nums1, 1)); println!("{}", three_sum_closest(&mut nums2, 1)); }
输出：
2
0
循环暴力法：
fn three_sum_closest(nums: &[i32], target: i32) -> i32 { let (mut res, mut dif) = (0, 20000); // 见提示中参数的范围，设置20000足够 for i in 0..nums.len() { for j in i+1..nums.len() { for k in j+1..nums.len() { let sum = nums[i] + nums[j] + nums[k]; let tmp = if sum < target { target - sum } else { sum - target }; if tmp < dif { dif = tmp; res = sum; } } } } res } fn main() { let nums1 = vec![-1, 2, 1, -4]; let nums2 = vec![0, 0, 0]; println!("{}", three_sum_closest(&nums1, 1)); println!("{}", three_sum_closest(&nums2, 1)); }
17. 电话号码的字母组合 Letter-combinations-of-a-phone-number
给定一个仅包含数字 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 <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
代码：
fn letter_combinations(digits: &str) -> Vec<String> { if digits.is_empty() { return vec![]; } let dict = vec![ vec![], // 0 vec![], // 1 vec!["a", "b", "c"], vec!["d", "e", "f"], vec!["g", "h", "i"], vec!["j", "k", "l"], vec!["m", "n", "o"], vec!["p", "q", "r", "s"], vec!["t", "u", "v"], vec!["w", "x", "y", "z"], ]; let mut res = vec!["".to_string()]; for digit in digits.chars() { let mut temp = Vec::new(); for s in &res { for c in &dict[digit.to_digit(10).unwrap() as usize] { temp.push(s.to_owned() + c); } } res = temp; } res } fn main() { println!("{:?}", letter_combinations("23")); println!("{:?}", letter_combinations("")); println!("{:?}", letter_combinations("2")); }
输出：
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
[]
["a", "b", "c"]
18. 四数之和 4Sum
给你一个由 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
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
代码：
fn four_sum(nums: &[i32], target: i32) -> Vec<Vec<i32>> { let mut nums = nums.to_vec(); nums.sort(); // 先排序 let mut res = Vec::new(); for i in 0..nums.len()-3 { if i > 0 && nums[i] == nums[i-1] { // 跳过重复的元素 continue; } for j in i+1..nums.len()-2 { if j > i+1 && nums[j] == nums[j-1] { // 跳过重复的元素 continue; } let (mut l, mut r) = (j+1, nums.len()-1); // 双指针 while l < r { let sum = nums[i] + nums[j] + nums[l] + nums[r]; if sum == target { res.push(vec![nums[i], nums[j], nums[l], nums[r]]); while l < r && nums[l] == nums[l+1] { // 跳过重复的元素 l += 1; } while l < r && nums[r] == nums[r-1] { // 跳过重复的元素 r -= 1; } l += 1; r -= 1; } else if sum < target { l += 1; } else { r -= 1; } } } } res } fn main() { println!("{:?}", four_sum(&[1, 0, -1, 0, -2, 2], 0)); println!("{:?}", four_sum(&[2, 2, 2, 2, 2], 8)); }
输出：
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
[[2, 2, 2, 2]]
