LeetCode代码刷题（17~24）_java

17. 电话号码的字母组合

18. 四数之和

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 <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

代码：


package com.my.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class letterCombinations {

    public static void main(String[] args) {
        String digits = "267";
        List result = letterCombinations(digits);

        System.out.println("数字字符串"+digits+"所能表示的字母组合为：");
        System.out.print("[");
        for(int i=0; i letterCombinations(String digits){
        List result = new ArrayList<>();
        if(digits == null && digits.length() == 0){
            return result;
        }

        Map phoneMap = new HashMap<>();
        phoneMap.put("2", new char[]{'a', 'b', 'c'});
        phoneMap.put("3", new char[]{'d', 'e', 'f'});
        phoneMap.put("4", new char[]{'g', 'h', 'i'});
        phoneMap.put("5", new char[]{'j', 'k', 'l'});
        phoneMap.put("6", new char[]{'m', 'n', 'o'});
        phoneMap.put("7", new char[]{'p', 'q', 'r', 's'});
        phoneMap.put("8", new char[]{'t', 'u', 'v'});
        phoneMap.put("9", new char[]{'w', 'x', 'y', 'z'});

        backTrack(result, phoneMap, digits, 0, new StringBuffer());
        return result;
    }

    public static void backTrack(List combinations, Map phoneMap, String digits, int index, StringBuffer combination){
        if(index == digits.length()){   //递归退出或结束条件。 递归中重要的一个条件，不然无法结束递归
            combinations.add(combination.toString());
        } else {
            String digit = digits.substring(index, index+1);
            char[] letters = phoneMap.get(digit);
            for(char letter: letters){
                combination.append(letter);
                backTrack(combinations, phoneMap, digits, index+1, combination);    //递归
                //重要！结束上面递归之后，去掉组合里的最后一位，进入下一轮循环。比如"23"的组合，上面的递归得出ad之后，到这一步，combination中去掉d，进入下一轮循环ae的情况
                combination.deleteCharAt(index);
            }
        }
    }
}

输出：

数字字符串267所能表示的字母组合为：
[amp,amq,amr,ams,anp,anq,anr,ans,aop,aoq,aor,aos,bmp,bmq,bmr,bms,bnp,bnq,bnr,bns,bop,boq,bor,bos,cmp,cmq,cmr,cms,cnp,cnq,cnr,cns,cop,coq,cor,cos]
一共有36种组合。

Process finished with exit code 0

18. 四数之和

题目：

给你一个由 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
-109 <= nums[i] <= 109
-109 <= target <= 109

代码：

package com.my.test;

import java.util.*;

public class fourSum {
    public static void main(String[] args) {
        System.out.println("待检查的数组为：");
        System.out.print("[");
        int[] array = {1,0,-1,0,-2,2};
        for(int i=0; i> result = fourSum(array, target);
        for (int j=0; j> fourSum(int[] nums, int target){
        //数组排序，升序
        Arrays.sort(nums);
        //数组长度
        int l = nums.length;
        // 定义Set集合，集合里放多个List(结果).
        // 利用Set去重的特性，确保里面保存的多个结果List不重复
        Set> hashSet = new HashSet<>();

        for(int i=0; i0 && nums[i] == nums[i-1]){
                continue;
            }

            //遍历数组
            for(int j=i+1; ji+1 && nums[j] == nums[j-1]){
                    continue;
                }

                while(left < right){
                    int sum = nums[i] + nums[j] +nums[left] + nums[right];
                    if(sum == target){  //如果sum==target, 即找到符合“4数之和等于目标值”的情况，则将4个数存到List, 然后添加到集合Set中
                       List list = new ArrayList<>();
                       list.add(nums[i]);
                       list.add(nums[j]);
                       list.add(nums[left]);
                       list.add(nums[right]);
                       hashSet.add(list);
                       //去重
                       while (lefttarget,说明此时四数之和大了,因为数组是升序,需要right下标向左移动,使4数之和变小
                        right--;
                    }
                }
            }
        }

        //因为返回值是一个List>, 所以这里需要将集合Set中的多个List, 添加到返回值List中
        ArrayList> result = new ArrayList<>();
        result.addAll(hashSet);

        return result;
    }
}