目录
LeetCode 第17题：电话号码的字母组合
LeetCode 第18题：四数之和
LeetCode 第17题：电话号码的字母组合
题目描述
给定一个仅包含数字2~9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。
2(abc)
3(def)
4(ghi)
5(jkl)
6(mno)
7(pqrs)
8(tuv)
9(wxyz)
示例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']的一个数字
解题思路：
方法一：回溯（深度优先搜索）
public class Solution {private readonly string[] phoneMap = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };//分别对应0~9public IList<string> LetterCombinations(string digits){List<string> result = new List<string>();//处理空字符串if(string.IsNullOrEmpty(digits)) return result;//使用StringBuilder优化字符串拼接StringBuilder current = new StringBuilder();Backtrack(digits,0,current,result);//自定义函数return result;}private void Backtrack(string digits,int index,StringBuilder current,List<string> result){//如果当前组合长度等于输入长度，添加到结果if(index==digits.Length) result.Add(current.ToString()),return;//获取当前数字对应的字母string letters phoneMap[digits[index]-'0'];//遍历当前数字对应的所有字母for(int i=0;i<letters.Length;i++) {current.Append(letters[i]);//递归处理下一个数字Backtrack(digits,index+1,current,result);//回溯，删除最后添加的字母current.Length--;}}}方法二：队列
public class Solution {private readonly string[] phoneMap = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public IList<string> LetterCombinations(string digits){List<string> result = new List<string>();//处理空字符串if(string.IsNullOrEmpty(digits)) return result;//初始化结果为空字符串result.Add("");//逐个处理每个数字foreach(char digit in digits){List<string> temp = new List<string>();string letters = phoneMap[digit - '0'];//将当前数字的每个字母与之前的结果组合foreach(string s in result){foreach(char letter in letters) temp.Add(s+letter);}result = temp;}return result;} }附加：遍历,看上去就很耗费时间，题目定义了数字组合最长为4
string phonemap[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; string nums; scanf("%c\n",&nums);for(int i=0;i<nums.Length;i++) {string current[i]=phonemap[nums[i]+1]; } for(int q=0;q<nums.Length;q++) {for(int j=0;j<current[q].Length;i++)printf("%c",current[q][i]);for(int k=0;k<current[q+1].Length;k++)printf("%c",current[q+1][k]);for(int p=0;p<current[q+2].Length;p++)printf("%c",current[q+2][p]);for(int m=0;m<current[q+3].Length;m++)printf("%c",current[q+3][m]); } }
LeetCode 第18题：四数之和
题目描述
给你一个由n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a],nums[b],nums[c],num[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
- 0<=a,b,c,d<n
- a,b,c,d互不相同
- nums[a]+nums[b]+nums[c]+nums[d]==target
你可以按任意顺序返回答案。
难度：中等
题目链接：18. 四数之和 - 力扣（LeetCode）
示例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
- -109<=nums[i]<=109
- -109<=target<=109
解题思路：固定两个数值，并移动两个指针进行移动
public class Solution{public IList<IList<int>> FourSum(int[] nums,int target){if(nums==null || nums.Length<4) return result;Array.Sort(nums);int n=nums.Length;//固定第一个数for(int i=0;i<n-3;i++){if(i>= && nums[i]==nums[i-1]) continue;if((long)nums[i]+nums[i+1]+nums[i+2]+nums[3]>target) break;if((long)nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;for(int j=i+1;j<n-2;j++){if(j>i+1 && nums[j]==nums[j-1]) continue;if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;if((long)nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;//双指针int left = j+1,right = n-1;while(left<right){long sum = (long)nums[i]+nums[j]+nums[left]+nums[right];if(sum==target) { result.Add(new List<int>{nums[i],nums[j],nums[left],nums[right]});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 result;}}
)
