代码随想录第六天

第三章 哈希表part02

今日任务

●  454.四数相加II

●  383. 赎金信

●  15. 三数之和

●  18. 四数之和

●  总结

详细布置

-------------------------------------------------------------------------------454.四数相加II---------------------------------------------------------------------------------------------

建议：本题是 使用map 巧妙解决的问题，好好体会一下 哈希法 如何提高程序执行效率，降低时间复杂度，当然使用哈希法 会提高空间复杂度，但一般来说我们都是舍空间 换时间， 工业开发也是这样。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html 

我的代码：

import java.util.*;

class Solution {

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        int res = 0;

        int n = nums1.length;

        Map<Integer, Integer> map1 = new HashMap<>();

        for(int i = 0; i < n; i ++){

            for(int j = 0; j < n; j ++){

                int sum = nums1[i] + nums2[j];

                if(map1.containsKey(sum)){

                    int v = map1.get(sum);

                    map1.put(sum, v + 1);

                }else{

                    map1.put(sum, 1);

                }

            }

        }

        for(int i = 0; i < n; i ++){

            for(int j = 0; j < n; j ++){

                int sum = nums3[i] + nums4[j];

                if(map1.containsKey(0 - sum)){

                    res += map1.get(0 - sum);

                }

            }

        }

        return res;

    }

}

map.put(sum, map.get(sum) + 1);

描述: 这段代码假设map中已经存在sum这个键，并试图获取该键对应的值并加1。

潜在问题: 如果sum不存在于map中，那么map.get(sum)将返回null，导致map.get(sum) + 1抛出NullPointerException。

适用场景: 适用于已经确保sum作为键在map中存在的情况。

2.map.put(sum, map.getOrDefault(sum, 0) + 1);

描述: 这段代码使用map.getOrDefault(sum, 0)，如果sum存在于map中，它返回对应的值；如果不存在，则返回默认值0。

优点: 不需要显式检查sum是否存在于map中，不存在时自动使用默认值0，并将值加1。

适用场景: 适用于需要处理键可能不存在的情况，代码更为健壮。

因此官方代码：


class Solution {

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        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);

            }

        }

        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数

        for (int i : nums3) {

            for (int j : nums4) {

                res += map.getOrDefault(0 - i - j, 0);

            }

        }

        return res;

    }

}


383. 赎金信

建议：本题 和 242.有效的字母异位词 是一个思路 ，算是拓展题

题目链接/文章讲解：https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

class Solution {

    public boolean canConstruct(String ransomNote, String magazine) {

        int[] hash = new int[26];

        if(ransomNote.length() > magazine.length()){

            return false;

        }

        for(int i : hash){

            i = 0;//这里取得值不是索引，而且默认值为0 不需赋值

        }

        for(int i = 0; i < ransomNote.length(); i ++){

            hash[ransomNote.charAt(i) - 'a'] ++;

        }

        for(int j = 0; j < magazine.length(); j ++){

            hash[magazine.charAt(j) - 'a'] --;

        }

        for(int i : hash){

            if(i > 0){

                return false;

            }

        }

        return true;

    }

}


补充：

for(charc:magazine.toCharArray())

{record[c-'a']+=1;}

15. 三数之和

建议：本题虽然和 两数之和 很像，也能用哈希法，但用哈希法会很麻烦，双指针法才是正解，可以先看视频理解一下 双指针法的思路，文章中讲解的，没问题 哈希法很麻烦。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html


class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i ++){

            if(nums[i] >= 0){

                return result;

            }

            if(i > 0 && nums[i] == nums[i-1]){

                continue;

            }

            int left = i + 1;

            int right = nums.length - 1;

            while(nums[i] + nums[left] + nums[right] > 0){

                right --;

            }

            while(nums[i] + nums[left] + nums[right] < 0){

                left ++;

            }

            while(nums[i] + nums[left] + nums[right] == 0){

                List<Integer> list = new ArrayList<>();

                list.add(nums[i]);

                list.add(nums[left]);

                list.add(nums[right]);

                result.add(list);

                left ++;

                right --;

                if(nums[left] == nums[left - 1]){

                    continue;}

            }

        }

        return result;

    }

}

报错：

java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 6

  at line 30, Solution.threeSum

  at line 56, __DriverSolution__.__helper__

  at line 86, __Driver__.main


更改：


class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i ++){

            if(nums[i] >= 0){

                return result;

            }

            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 --;}

                if(sum < 0){left ++;}

                while(sum == 0){

                    List<Integer> list = new ArrayList<>();

                    list.add(nums[i]);

                    list.add(nums[left]);

                    list.add(nums[right]);

                    result.add(list);

                    left ++;

                    right --;

                    if(nums[left] == nums[left - 1]){

                        continue;}

                }

            }

        }

        return result;

    }

}

改为 while(sum == 0 && left < right){ 可运行

再改：


class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i ++){

            if(nums[i] > 0){

                return result;

            }

            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 --;}

                if(sum < 0){left ++;}

                while(sum == 0 && left < right){

                    List<Integer> list = new ArrayList<>();

                    list.add(nums[i]);

                    list.add(nums[left]);

                    list.add(nums[right]);

                    result.add(list);

                    left ++;

                    right --;

                    if(nums[left] == nums[left - 1]){

                        left ++;

                        right --;}

                    if(left < right){

                        sum = nums[i] + nums[left] + nums[right];

                    }

                }

            }

        }

        return result;

    }

}

我的最终修改版：

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i ++){

            if(nums[i] > 0){

                return result;

            }

            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 --;}

                if(sum < 0){left ++;}

                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 --;

                    if(nums[left] == nums[left - 1]){

                        left ++;}

                    if(nums[right] == nums[right + 1]){

                        right --;}

                }

            }

        }

        return result;

    }

}

[-2,0,3,-1,4,0,3,4,1,1,1,-3,-5,4,0]

添加到测试用例

输出

[[-5,1,4],[-5,1,4],[-3,-1,4],[-3,0,3],[-2,-1,3],[-2,1,1],[-1,0,1],[-1,0,1],[0,0,0]]

预期结果

[[-5,1,4],[-3,-1,4],[-3,0,3],[-2,-1,3],[-2,1,1],[-1,0,1],[0,0,0]]


class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i ++){

            if(nums[i] > 0){

                return result;

            }

            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 --;}

                if(sum < 0){left ++;}

                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(nums[left] == nums[left - 1] && left < right){

                        left ++;}

                    while(nums[right] == nums[right + 1] && left < right){

                        right --;}

                }

            }

        }

        return result;

    }

}

18. 四数之和

建议： 要比较一下，本题和 454.四数相加II 的区别，为什么 454.四数相加II 会简单很多，这个想明白了，对本题理解就深刻了。 本题 思路整体和 三数之和一样的，都是双指针，但写的时候 有很多小细节，需要注意，建议先看视频。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html


class Solution {

    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        for(int k = 0; k < nums.length; k ++){

            if(nums[k] > target && nums[k] > 0 && target > 0){

                    return result;

                }

                if(k > 0 && nums[k] == nums[k-1]){

                    continue;

                }

            for(int i = k + 1; i < nums.length; i ++){

                if(nums[k] + nums[i] > target && nums[k] + nums[i] > 0 && target > 0){

                    return result;

                }

//去重不能去早了

                if(i >  k + 1 && nums[i] == nums[i-1]){

                    continue;

                }

                int left = i + 1;

                int right = nums.length - 1;

                while(left < right){

                    int sum = nums[k] + nums[i] + nums[left] + nums[right];

                    if(sum > target){right --;}

                    if(sum < target){left ++;}

                    if(sum == target){

                        List<Integer> list = new ArrayList<>();

                        list.add(nums[k]);

                        list.add(nums[i]);

                        list.add(nums[left]);

                        list.add(nums[right]);

                        result.add(list);

                        left ++;

                        right --;

                        while(nums[left] == nums[left - 1] && left < right){

                            left ++;}

                        while(nums[right] == nums[right + 1] && left < right){

                            right --;}

                    }

                }

            }

        }

        return result;

    }

}


结果：

nums =

[-9,-2,7,6,-8,5,8,3,-10,-7,8,-8,0,0,1,-8,7]

target =

4

添加到测试用例

输出

[[-10,-2,8,8],[-10,0,6,8],[-10,0,7,7],[-10,1,5,8],[-10,1,6,7],[-10,3,5,6],[-9,-2,7,8],[-9,0,5,8],[-9,0,6,7],[-9,1,5,7],[-8,-2,6,8],[-8,-2,7,7],[-8,0,5,7],[-8,1,3,8],[-8,1,5,6],[-7,-2,5,8],[-7,-2,6,7],[-7,0,3,8],[-7,0,5,6],[-7,1,3,7],[-2,0,0,6],[-2,0,1,5]]

预期结果

[[-10,-2,8,8],[-10,0,6,8],[-10,0,7,7],[-10,1,5,8],[-10,1,6,7],[-10,3,5,6],[-9,-2,7,8],[-9,0,5,8],[-9,0,6,7],[-9,1,5,7],[-8,-2,6,8],[-8,-2,7,7],[-8,0,5,7],[-8,1,3,8],[-8,1,5,6],[-7,-2,5,8],[-7,-2,6,7],[-7,0,3,8],[-7,0,5,6],[-7,1,3,7],[-2,0,0,6],[-2,0,1,5],[0,0,1,3]]

class Solution {

    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        for(int k = 0; k < nums.length; k ++){

            if(nums[k] > target && nums[k] > 0 && target > 0){

                    return result;

                }

                if(k > 0 && nums[k] == nums[k-1]){

                    continue;

                }

            for(int i = k + 1; i < nums.length; i ++){

                if(nums[k] + nums[i] > target && nums[k] + nums[i] > 0 && target > 0){

                     break;// 你跳出当前循环可以 别都跳了

                }

//去重不能去早了

                if(i >  k + 1 && nums[i] == nums[i-1]){

                    continue;

                }

                int left = i + 1;

                int right = nums.length - 1;

                while(left < right){

                    long sum = (long)nums[k] + nums[i] + nums[left] + nums[right];

                    if(sum > target){right --;}

                    if(sum < target){left ++;}

                    if(sum == target){

                        List<Integer> list = new ArrayList<>();

                        list.add(nums[k]);

                        list.add(nums[i]);

                        list.add(nums[left]);

                        list.add(nums[right]);

                        result.add(list);

                        left ++;

                        right --;

                        while(nums[left] == nums[left - 1] && left < right){

                            left ++;}

                        while(nums[right] == nums[right + 1] && left < right){

                            right --;}

                    }

                }

            }

        }

        return result;

    }

}

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,233评论 6赞 495
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,357评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,831评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,313评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,417评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,470评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,482评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,265评论 0赞 269
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,708评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,997评论 2赞 328
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,176评论 1赞 342
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,827评论 4赞 337
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,503评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,150评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,391评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,034评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,063评论 2赞 352

推荐阅读更多精彩内容