923打卡

1. 三数之和 （15）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
      List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int first = 0; first < nums.length; first++) {
            if(first>0 && nums[first] == nums[first-1])
                continue;
            int third = nums.length-1;
            int target = -nums[first];
            for (int second = first+1; second <third ; second++) {
                if(second>first+1 && nums[second] ==nums[second-1])
                    continue;
                while(second<third && nums[second]+nums[third] > target)
                    third--;
                if(second == third)
                    break;
                if ( nums[second]+nums[third]==target){
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    res.add(list);
                }
            }
        }
        return res;
    }
}

2. 最接近的三数之和（16）

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
  int best = Integer.MAX_VALUE;
  Arrays.sort(nums);
        for (int first = 0; first < nums.length ; first++) {
            if(first>0 && nums[first]==nums[first-1])
                continue;
            int second = first+1;
            int third = nums.length-1;


            while ( second <third) {

                int sum  = nums[first]+nums[second]+nums[third];
                if(sum ==target)
                    return sum;

                if( Math.abs(sum-target) <Math.abs(best-target)){
                    best = sum;
                }
                if (sum >target){
                    int right = third-1;
                    while (second<right && nums[right]== nums[third])
                        right--;
                    third =right;
                }else {
                    int left = second + 1;
                    while (left < third && nums[left] == nums[second])
                        left++;
                    second = left;
                }
            }
        }
            return best;
        }

}

3. 电话号码的组合（17）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

class Solution {
     public List<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0)
            return res;
        StringBuffer combination = new StringBuffer();
        backstack(res, digits, 0, combination);
        return res;
    }

    HashMap<Character, String> map = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");

    }};

    private void backstack(ArrayList<String> res, String digits, int index, StringBuffer combination) {
        if (index == digits.length())
            res.add(combination.toString());
        else {
            String letters = map.get(digits.charAt(index));
            for (int i = 0; i < letters.length(); i++) {
                combination.append(letters.charAt(i));
                backstack(res, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }


    }
}

4. 四数之和（18）

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
     ArrayList<List<Integer>> list = new ArrayList<>();
        if (nums == null || nums.length < 4) return list;
        Arrays.sort(nums);
        for (int i = 0; i <= nums.length - 4; i++) {
            //剪枝
            if (nums[i] > 0 && nums[i] > target) {
                break;
            }
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j <= nums.length - 3; j++) {
                //剪枝,考虑数组元素有负数
                if (nums[i] + nums[j] > target && target > 0) {
                    break;
                }
                //去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    if (nums[i] + nums[j] + nums[left] + nums[right] < target) {
                        left++;
                    } else if (nums[i] + nums[j] + nums[left] + nums[right] > target) {
                        right--;
                    } else {
                        ArrayList<Integer> res = new ArrayList<>();
                        res.add(nums[i]);
                        res.add(nums[j]);
                        res.add(nums[left]);
                        res.add(nums[right]);
                        list.add(res);
                        while (right > left && nums[right] == nums[right - 1])
                            right--;
                        while (right > left && nums[left] == nums[left + 1])
                            left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return list;

    }
}