当前位置：首页 > article >正文

[代码随想录打卡Day7] 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

article 2024/11/6 1:22:44

454.四数相加

思路：没有去重问题，使用化解法。先对a,b两个数组进行双层for循环遍历得到所有的a+b的值保存到map中，key是a+b的值，value存储出现的次数，然后双层for循环遍历c,d，查找0-(c+d)是否在map中，如果在map中就count+=value。
列一下JAVA，Python和C++代码。

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //先对a,b数组进行遍历保存a+b的值以及出现的此时
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入到map
        for(int i : nums1){
            for(int j: nums2){
                int sum = i+j;
                map.put(sum, map.getOrDefault(sum, 0)+1);//getOrDefault应该如果存在就get相应的值，如果不存在就使用默认值，默认值设置是0
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for(int i : nums3){
            for(int j : nums4){
                res += map.getOrDefault(0-i-j,0);
            }
        }
        return res;
    }
}

class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type nums3: List[int]
        :type nums4: List[int]
        :rtype: int
        """
        hashmap = dict()
        for n1 in nums1:
            for n2 in nums2:
                if n1+ n2 in hashmap:
                    hashmap[n1+n2] += 1
                else:
                    hashmap[n1+n2] = 1#如果在就加1，不在就赋值为1
        #如果 -(n1+n2)存在于nums3和nums4，存入结果
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = -n3-n4
                if key in hashmap:
                    count += hashmap[key]
        return count

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
                unordered_map<int, int> umap;//key:a+b的数值，value:a+b数值出现的次数
        //遍历大A和大B数组，统计两个数组元素之和，和出现的此时，放到map中
        for(int a: nums1){
            for(int b: nums2){
                umap[a+b]++;
            }
        }//把两个数的和放到map中相应的value++，统计次数
        int count = 0;//统计a+b+c+d=0出现的此时
        //再遍历大C和大D数组，找到如果0-(c+d)在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for(int c: nums3){
            for(int d: nums4){
                if(umap.find(0-(c+d))!=umap.end()){
                    count += umap[0-(c+d)];
                }
            }
        }
        return count;
    }
};

II 383. 赎金信

和字母异位词太像了。就是判断条件变了，字母异位词是record数组中全是0，这个是先遍历magazine再遍历ransomNote要求record数组中大于等于0。
列一下JAVA和C++代码。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        //这个题目说所有都是小写字母，所以用数组比较有效
        if(ransomNote.length() > magazine.length()){
            //如果长度直接不够就不用遍历了
            return false;
        }
        int[] record = new int[26];
        //遍历，遍历magazine中的字符如果存在就是把相应的字符的数量佳佳
        for(char c : magazine.toCharArray()){
            //变成char类型的数组
            record[c-'a']+=1;
        }
        for(char c: ransomNote.toCharArray()){
            record[c-'a'] -=1;
        }
        for(int i : record){
            if(i < 0){
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        //又是表明了使用小写字母，可以使用数组的就使用数组
        int record[26] = {0};//初始化一下
        //add
        if (ransomNote.size() > magazine.size()){
            return false;
        }
        for(int i =0; i < magazine.length(); i++){
            //通过record数据记录magazine里各个字符出现的次数
            record[magazine[i] - 'a']++;//
        }//数组的索引是值，数组的值是出现的次数
        //感觉和字母异位词相似，就是看字母够不够用
        for(int j =0; j < ransomNote.length(); j++){
            //遍历ransomnOTE，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            if (record[ransomNote[j]-'a']<0){
                return false;
            }
        }
        return true;
    }
};

15. 三数之和

先排序，然后遍历i得到a，再i到num.size-1的区域引入对撞指针left,right就是在区间两端分别代表b,c。如果a+b+c>0就将right–，a+b+c<0就将left++,a+b+c=0就保存结果然后进行去重操作就是将left和right从当前位置移动到和当前数值相同的最靠近中间的位置，然后right–,left++进行下一轮寻找。
JAVA和C++写起来差不多，思想相同。
JAVA

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //双指针
        List<List<Integer>> result = new ArrayList<>();//这个就是生成结果列表，每个三元组的结果是有一个list组成的，多个List组成的result就是存放多个三元组的结果列表
        Arrays.sort(nums);
        //找出a+b+c=0
        //a = nums[i],b = nums[left],c = nums[right]
        for(int i = 0; i < nums.length; i++){
            //排序后如果第一个元素已经大于0，那么无论如何组合不可能凑成三元组，直接返回结果
            if(nums[i]>0){
                return result;
            }

            if(i >0 && nums[i] == nums[i -1]){//对a去重
                continue;
            }
            int left = i+1;
            int right = nums.length -1;
            while(right > left){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0){
                    right--;
                }else if (sum < 0){
                    left++;
                }else{
                    result.add(Arrays.asList(nums[i], nums[left],nums[right]));
                    //对b,c去重，下面两个while语句，把right移动到与当前值相同的最前面那个位置，left移动到与当前值相同的最后的一个位置
                    while(right > left && nums[right] == nums[right-1]) right--;
                    while(right > left && nums[left] == nums[left + 1]) left++;
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());//先对数组进行排序
        //找出a+b+c=0
        //a = nums[i],b = nums[left],c=nums[right]
        for(int i =0; i< nums.size(); i++){
            //如果排序之后第一个元素已经大于0， 那么无论如何组合都不可能凑成三元组，直接返回结果
            if(nums[i]>0){
                return result;
            }
            //去重a，a的循环中已经找到了所有的和a相加等于0的b,c的组合，所以如果有重复的，就把i++
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            int left = i +1;
            int right = nums.size()-1;
            //就是把i当作遍历过的数从后面的数中寻找b,c使得a+b+c等于0
            while(right > left){
                //找到结果了再对b,c进行去重，为了防止直接去重把有重复数字的结果给Pass了
                if(nums[i]+nums[left]+nums[right]>0) right--;
                else if(nums[i]+nums[left]+nums[right]<0) left++;
                else{
                    //就是找到相应的三元组了，就是先把结果保存
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    //去重逻辑应该放到找到一个三元组之后，对b,c去重
                    while(right > left && nums[right] == nums[right]-1) right--;//这个是将right移动到最前面那个和right值相等的位置，
                    while(right > left && nums[left] == nums[left + 1]) left++;

                    //找到答案时， 双指针同时收缩、
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};

18. 四数之和

考虑到剪枝去重操作。明天再消化。列上C++代码。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for(int k = 0; k <nums.size(); k++){
            //剪枝处理
            if(nums[k]>target && nums[k]>=0){
                break;//这里使用break，统一使用最后的return返回
            }
            //对nums[k]去重
            if(k > 0 && nums[k] == nums[k-1]){
                continue;
            }
            for(int i = k+1; i<nums.size();i++){
                //二级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }
                //对nums[i]去重
                if(i>k+1 && nums[i]==nums[i-1]){
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
};