算法训练营（day07）

454.四数相加II

题目链接：https://leetcode.cn/problems/4sum-ii/description/

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

解题思路

解题过程：

定义一个 res 用于统计元组个数
遍历 nums1 和 nums2 数组，定义一个 map，key放**nums1[i]和nums2[j]两数之和，value 放nums1[i]和nums2[j]两数之和出现的次数**
遍历 nums3 和 nums4 数组
- 如果 0 - (nums3[k] + nums4[l]) 在 map 中出现过，就用 res 把 map 中 0 - (nums3[k] + nums4[l]) 对应的 value 累加。
最后返回统计值 res

详细代码

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for(int i : nums1){
            for(int j : nums2){
                int tmp = i + j;
                map.put(tmp, map.getOrDefault(tmp, 0) + 1);
            }
        }
        for(int i : nums3){
            for(int j : nums4){
                int count = i + j;
                if(map.containsKey(0 - count)){
                    res += map.get(0 - count);
                }
            }
        }
        return res;
    }
}

383.赎金信

题目链接：https://leetcode.cn/problems/ransom-note/description/

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

解题思路

解题过程：

题目给定了字符仅由小写字符组成，且杂志(magazine)里面的字母不可重复使用
用数组存储 magazine 的字符
如果 ransomNote 出现了 magazine 的字符，则将 magazine 的字符删去
遍历一遍 ransomNote 后，判断 magazine 的字符长度
- 如果 < 0，则说明不满足题意，返回 false
- 否则返回 true

详细代码

解法一：用 magazine 字符串作参照，< 0 为 false

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] res = new int[26];

        for(char c : magazine.toCharArray()){
            res[c - 'a']++;
        }
        for(char c : ransomNote.toCharArray()){
            res[c - 'a']--;
        }
        for(int count : res){
            if(count < 0){
                return false;
            }
        }
        return true;
    }
}

解法二：用 ransomNote 字符串作参照，> 0 为 false

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] res = new int[26];

        for(char c : ransomNote.toCharArray()){
            res[c - 'a']++;
        }
        for(char c : magazine.toCharArray()){
            res[c - 'a']--;
        }
        for(int count : res){
            if(count > 0){
                return false;
            }
        }
        return true;
    }
}

15.三数之和

题目链接：https://leetcode.cn/problems/3sum/description/?orderBy=most_votes

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解题思路

解题过程：

不可以包含重复，说明需要对三元组进行去重操作
首先对数组排序，如果 nums[0] 已经 > 0，直接返回空（剪枝）
使用双指针的方法，对于 j、k 用指针 left, right 代替，只需要保证三元素不重复即可
关键是去重的操作，要注意当 nums 有且仅有三个元素 、 有元素重复 且 满足题意 的情况（需保留）
- i > 0 && nums[i] == nums[i - 1]
- left < right && nums[right] == nums[right - 1]
- left < right && nums[left] == nums[left + 1]
循环结束后，返回结果 res.add(Arrays.asList(nums[i], nums[left], nums[right]))

详细代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                return res;
            }
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];

                if(sum > 0){
                    right--;
                }else if(sum < 0){
                    left++;
                }else{
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    while(left < right && nums[right] == nums[right - 1]){
                        right--;
                    }
                    while(left < right && nums[left] == nums[left + 1]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return res;
    }
}

18.四数之和

题目链接：https://leetcode.cn/problems/4sum/description/

给你一个由 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

你可以按 任意顺序 返回答案。

解题思路

解题过程：

四数之和和 15.三数之和是一个思路，都是 先排序再使用双指针法，基本解法就是在 三数之和 的基础上再套一层for循环
关键点还是去重和剪枝

详细代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > target && nums[i] > 0){
                return res;
            }
            if(i > 0 && nums[i - 1] == nums[i]){
                continue;
            }

            for(int j = i + 1; j < nums.length; j++){
                if(j > i + 1 && nums[j - 1] == nums[j]){
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while(left < right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum == target){
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                        while(left < right && nums[right - 1] == nums[right]){
                            right--;
                        }
                        while(left < right && nums[left + 1] == nums[left]){
                            left++;
                        }
                        right--;
                        left++;
                    }else if(sum > target){
                        right--;
                    }else{
                        left++;
                    }
                }
            }
        }
        return res;
    }
}