代码随想录算法训练营第七天|454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和、总结

第454题，四数加III

扣除主题链接(opens new window)

给定四个包含整数的数组列表A , B , C , D ,计算多少个元组 (i, j, k, l)，使得A[i] + B[j] + C[k] + D[l] = 0。

为了简化问题，一切 A, B, C, D 长度N相同，长度N相同 0 ≤ N ≤ 500 。所有整数的范围都在 -2^28 到 2^28 - 1 最终结果不超过2^31 - 1 。

例如:

输入:

• A = [ 1, 2]
• B = [-2,-1]
• C = [-1, 2]
• D = [ 0, 2]

输出:

2

解释:

两个元组如下：

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

思路：

四数加，考虑用两个for循环来表示两两加，用哈希表的map集合来保存key-value结构，key表示元素和，value表示和出现的次数。

回到map的getordefault()方法 key 相映射的的 value，如果给定的 key 如果在映射关系中找不到，则返回指定的默认值。

class Solution {    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {        int res = 0;    ///用来表示最终结果        Map<Integer, Integer> map = new HashMap<>();   ///key表示元素和，value表示出现的次数        for(int i : nums1){            for(int j : nums2){                int sum = i+j;                map.put(sum, map.getOrDefault(sum, 0)+1);    //统计数组1和数组2中的元素和次数，不在乎重复与否，因为不在乎重复与否            }        }        for(int m : nums3){            for(int n : nums4){                res += map.getOrDefault(0-m-n, 0);   ///不用担心顺序，可以和次数相交。            }        }        return res;    }}

扣除主题链接(opens new window)

给定赎金信 (ransom) 字符串和杂志(magazine)判断字符串的第一个字符串 ransom 可以用第二个字符串吗？ magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(标题描述:为了不暴露赎金信的字迹，从杂志上搜索所需的字母，形成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设这两个字符串只包含小写字母。

canConstruct("a", "b") -> falsecanConstruct("aa", "ab") -> falsecanConstruct("aa", "aab") -> true

思路：

首先，我们需要了解tochararray()的方法 将字符串转换为字符数组的方法。

起初，我试图用map来解决这个问题。这个想法很简单。首先，将magazine上的所有字符串元素放入哈希表中，然后每个字符串元素出现在ransom上，在哈希表的相应位置减去1，最后遍历哈希表的value值，出现小于0的即false。

class Solution {    public boolean canConstruct(String r, String m) {        ///key保留元素，value保留出现的次数        if(r.length() > m.length()) return false;        Map<Character, Integer> map = new HashMap<>();        for(int i = 0; i < m.length(); i++){            map.put(m.charAt(i), map.getOrDefault(m.charAt(i), 0)+1);        }        for(int j = 0; j < r.length(); j++){            map.put(r.charAt(j), map.getOrDefault(r.charAt(j), 0)-1);        }        for(Integer value : map.values()){            if(value < 0){                return false;            }        }        return true;    }}

后来，我看了问题解决方案，了解到如果使用map，空间消耗大于数组，map需要维护红黑树或哈希表，并制作哈希函数，这需要时间。使用数组类似于以前的有效字母异位词

class Solution {    public boolean canConstruct(String r, String m) {        int[] res = new int[26];        if(r.length() > m.length()){            return false;        }        for(char c : m.toCharArray()){            res[c - 'a']++;        }        for(char c : r.toCharArray()){            res[c - 'a']--;        }        for(int i : res){            if(i < 0){                return false;            }        }        return true;    }}

扣除主题链接(opens new window)

给你一个包含 n 一个整数数组nums，判断nums中是否有三个元素 a，b，c ，使得a + b + c = 0 ？请找出所有符合条件且不重复的三元组。

注：重复的三元组不能包含在答案中。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组合为： [ [-1, 0, 1], [-1, -1, 2] ]

思路：

双指针方法，这个问题很难解决，在解决问题之前没有想法，在解决问题之后，不明白为什么我们需要把B和C重放到一个三元组。例如，如果排名后的数组是[0 , -1, -1, -1, -1, 1, 1, 1, 1] ， 可以理解，重复元素只有在三元组存在后才能跳过。

class Solution {    public List<List<Integer>> threeSum(int[] nums) {        List<List<Integer>> res = new ArrayList<>();        Arrays.sort(nums);        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){                if(nums[i]+nums[left]+nums[right] < 0){                    left++;                }else if(nums[i]+nums[left]+nums[right] > 0){                    right--;                }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;    }}

扣除主题链接(opens new window)

题意:给定一个包含n的包含 一个整数数组nums和一个目标值target，判断nums中是否有四个元素 a，b，c和 d，使得a + b + c + d值等于target？找出所有符合条件且不重复的四元组。

注意：

重复的四元组不能包含在答案中。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路：

就像三数之和一样，使用双指针需要在外面设置一层循环。

去重剪枝和三数之和一样，但不同的是，因为这个target是任意数，所以只有nums[i]正数时，如果大于target，可以剪枝。

还要考虑sum和数据的类型，如果使用int会超过，则应将其改为long

class Solution {    public List<List<Integer>> fourSum(int[] nums, int target) {        List<List<Integer>> res = new ArrayList<>();        Arrays.sort(nums);        for(int i = 0; i < nums.length; i++){            if(nums[i] > 0 && nums[i] > target){                continue;            }            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;                int right = nums.length-1;                while(left < right){                    long sum = (long)(nums[i]+nums[j]+nums[left]+nums[right]);                    if(sum < target){                        left++;                    }else if(sum > target){                        right--;                    }else{                        res.add(Arrays.asList(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--;                    }                }            }        }        return res;    }}