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

454.四数相加Ⅱ

思路

• 题目中给出了四个数组如果用hash的方式的解法的话可以先遍历前两个数组相加,并把每次加出来的和出现的次数记录在哈希表中
• 同样的方式遍历后两个数组找出0减去每两位相加的和是否存在与哈希表中如果存在累加次数

实现中遇到的问题：第一次实现时分别记录了前两个数组和后两个数组的哈希表然后相加最后结果是多算了的，其实在遍历后两个数组时就是找后两个数组每次组合对应的前两个数组的所有可能所以不用记录两个数组了

• 时间复杂度：O(num1num2)+O(num3num4) = O(n^2)
• 空间复杂度:要创建哈希表的空间

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> mapA = new HashMap<>();
        for (int i : nums1) {
            for (int i1 : nums2) {
                int temp = i+i1;
                if (mapA.containsKey(temp)){
                    mapA.put(temp,mapA.get(temp)+1);
                }else{
                    mapA.put(temp,1);
                }
            }
        }
        int count = 0;
        for (int i : nums3) {
            for (int i1 : nums4) {
                int temp = i+i1;
                if (mapA.containsKey(0-temp)){
                    count+=mapA.get(0-temp);
                }
            }
        }

        return count;

    }
}

383.赎金信

思路

1. 题目中明确字符串内全小写遂可以通过数组的方式记录ransomNote中每个字母出现的次数,假设保存为数组a
2. 然后遍历magazine中的每个字母并对数组a中相应字母次数减一操作
3. 遍历完两个字符串后访问数组a看哪一位字母在减一操作后还大于0,如果有大于0的证明magazine中的字母不够组合ransomNote

• 时间复杂度:O(n+m+26)===O(n)
• 空间复杂度:O(26)===O(1)

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {

        //题目中全小写字母
        int[] a = new int[26];

        for (char c : ransomNote.toCharArray()) {
            a[c-'a']++;
        }

        for (char c : magazine.toCharArray()) {
            a[c-'a']--;
        }

        for (int i : a) {
            if (i>0){
                return false;
            }
        }

        return true;
    }
}

15.三数之和

思路

• 这道题因为要考虑驱虫通过所以用哈希解的话会有很多问题很难控制边界条件
• 使用双指针也许是最优解:

1. 首先要对数组升序排序
2. 遍历数组的每一位以及寻找相应的左右指针使得三者之和为0,假设当前遍历索引为i,左指针索引为left右指针索引为right,那么:nums[i]+left+right = 0;
3. 其中左指针起始位置为i+1,如果三者和小于0,left++
4. 右指针的起始位置为length-1,如果三者和大于0,right–;
5. 如果三者和等于0保存,指针向中间靠拢寻找下一组nums[i]+left+right=0;
6. 需要注意存储三元组后要去除后面的左右指针分别与当前保存下来的左右指针相等的指针,直至left<=right;
7. 自此针对i的一轮循环结束,i++进入下轮循环,找寻符合条件的i+1对应的左右指针

• 时间复杂度:O(n^2)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        //双指针 nums[i]+left+right = 0
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]>0){ //如果第一位就大于0 那么后面就不可能组成加一块等于0的三元组
                break;
            }
            if (i>0 //保留第一位,从第二个开始去除重复
                    && nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while (left<right){ //left=righ那么三元组后两位为同一个不成立所以要排除
                int sum = nums[i]+nums[left]+nums[right];
                if (sum == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    //加入结果集后要对left和right去重
                    while (left<right && nums[left] == nums[left+1]) left++;
                    while (left<right && nums[right] == nums[right-1]) right--;
                    //加入结果集后进入下一循环左右指针前移
                    left++;
                    right--;
                }else if (sum<0){
                    left++;
                }else if (sum>0){
                    right--;
                }
            }
        }
        return result;
    }
}

18.四数之和

思路

• 四数之和就是在三数之和的基础上外面再加一层for循环

• 四数\三数之和双指针解法就是把最后两位用指针的方法查找,也就是看对比暴力解法少了一层for循环

• 时间复杂度:O(n^3)

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //剪枝
            if (nums[i]>target && nums[i]>=0){
                break;
            }
            //i去重
            if (i>0 && nums[i] == nums[i-1]){
                continue;
            }
            for (int j = i+1; j < nums.length; j++) {
                //剪枝
                if (nums[i]+nums[j]>target && nums[i]+nums[j]>=0){
                    break;
                }
                //j去重
                if (j>i+1 && nums[j] == nums[j-1]){
                    continue;
                }
                int left = j+1;
                int right = nums.length-1;
                while (left<right){
                    int temp = nums[i]+nums[j]+nums[left]+nums[right];
                    if (temp == target){
                        List<Integer> tempList = new ArrayList<>();
                        tempList.add(nums[i]);
                        tempList.add(nums[j]);
                        tempList.add(nums[left]);
                        tempList.add(nums[right]);
                        list.add(tempList);

                        //去重
                        while (left<right && nums[left] == nums[left+1]) left++;
                        while (left<right && nums[right] == nums[right-1]) right--;

                        //向中间靠拢
                        left++;
                        right--;
                    }else if (temp<target){
                        left++;
                    }else  {
                        right--;
                    }
                }
            }
        }
        return list;
    }
}