力扣第17题电话号码的字母组合和第18题四数之和
题目：
思路：
1.排列组合一般都是用回溯算法来计算的 2.先对输入的进行为null和空判断 3.使用map存入键值对，先从下边为0开始遍历，使用递归，当组合数长度等于输入的长度时代表组合完成
class Solution {
public List<String> letterCombinations(String digits) {
List<String> lists=new ArrayList<>();
if(digits==null||digits.length()==0){
return lists;
}
HashMap<Character,String> phone =new HashMap<>();
phone.put(2,"abc");
phone.put(3,"def");
phone.put(4,"ghi");
phone.put(5,"jkl");
phone.put(6,"mno");
phone.put(7,"pqrs");
phone.put(8,"tuv");
phone.put(9,"wxyz");
//回溯
backTrack(lists,phone,digits,0,new StringBuffer());
return lists;
}
private void backTrack(List<String> lists, HashMap<Character, String> phone, String digits, int index, StringBuffer combination) {
if(index==digits.length()){
lists.add(combination.toString());
}else {
char ch =digits.charAt(index);
String letters =phone.get(ch);
int lettersCount =letters.length();
for (int i=0;i<lettersCount;i++){
combination.append(letters.charAt(i));
backTrack(lists,phone,digits,index+1,combination);
combination.deleteCharAt(index);
}
}
}
}
题目：
思路：
1.跟之前的三数之和一样，使用双指针， 2.然后使用循环先固定两个数，与双指针的数相加为零。 3.先进行排序，同时还要去重。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1, right = nums.length - 1;
while (left < right) {
while (left > j + 1 && left < nums.length && nums[left] == nums[left - 1]) left++;
if (left >= right) break;
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
list.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
left++;
} else if (sum > target) {
right--;
} else if (sum < target) {
left++;
}
}
}
}
return list;
}
}
