代码随想录算法训练营第7天

454.四数相加

题目链接:454. 四数相加 II - 力扣(LeetCode)

视频/文档链接:代码随想录 (programmercarl.com)

第一想法

遍历数组num1,num2,计算其和出现的数量,放入map集合中,键为和,值为出现的次数。遍历num3,num4,0-若其和的值出现在Map集合中,则count+=该值即可。

可优化点

不熟悉调用mapAPI。

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

代码

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i : nums1){
            for(int j:nums2){
                int sum = i+j;
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
        }
        for (int k : nums3) {
            for (int n : nums4) {
                int sum = k+n;
                if(map.containsKey(-sum)){
                    count+=map.get(-sum);
                }
            }
        }
        return count;
    }
}

383.赎金信

 题目链接:383. 赎金信 - 力扣(LeetCode)

视频/文档链接:代码随想录 (programmercarl.com)

第一想法

这个题和力扣242题很像。

对于案例:ransomNote = "aa", magazine = "aab"

力扣242:字符串s和t每个字母出现的次数都必须一样。所以返回false

力扣383:只要求ransdomNote每个字母数量<=magazine,则返回true。

代码

一次过。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] ransdomArr = new int[26];
        int[] magazineArr = new int[26];
        for (int i = 0; i < ransomNote.length(); i++) {
            ransdomArr[ransomNote.charAt(i)-'a']++;
        }
        for (int j = 0; j < magazine.length(); j++) {
            magazineArr[magazine.charAt(j)-'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if(ransdomArr[i]>magazineArr[i])
                return false;
        }
        return true;
    }
}

15.三数之和

题目链接:15. 三数之和 - 力扣(LeetCode)

文档/视频链接:代码随想录 (programmercarl.com)

第一想法

a+b+c = 0,直接暴力循环然后去重。
a从第1个元素遍历,b从i+1处遍历,然后c的值应为-(a+b),看map集合中是否存在。最终去除重复元素。

代码随想录想法

首先先将数组排序,一层for循环,i代表当前元素a,再定义left指针b和right指针c,

若相加之和>0,则right--,相加之和<0,left++,相加之和 = 0,则加入结果集。直到left = right终止循环,相等时无意义。

当去重a时需要判断 if(nums[i] != nums[i-1]),即当前元素与之前元素不同,那么第一个元素不是会报空指针异常么,怎么避免这个问题?按照这样就能避免对 i= 0 时进行判定了。

  if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
          continue;
  }

每次遍历对第一个元素要都判断是否>0,所以nums[i]>0这个判断逻辑要加到循环里面。还有个细节是直接return,而不是continue了。因为已经排序的数组,一旦碰上正数,往后的也必须是正数。

关于b和c的去重

我在看视频的时候也想的是直接将去重逻辑提前。

 if (nums[i] + nums[left] + nums[right] > 0) {
        right--;
        // 去重 right
        while (left < right && nums[right] == nums[right + 1]) right--;
    } else if (nums[i] + nums[left] + nums[right] < 0) {
        left++;
        // 去重 left
        while (left < right && nums[left] == nums[left - 1]) left++;
    } else {
    }

但对提升效率没有帮助,反正去重也是一个一个减下去,在哪里减都是一样的。

索性放在else中,结构更好看一点。

同时去重时还要判断left<right,是为了防止指针越界需要加上。可以记小模版就是while(left<right)再套while循环,里面while条件要考虑加外层循环条件。

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> endResult = new ArrayList<>();
        Arrays.sort(nums);//排序
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0)
                return endResult;
            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)
                    right--;
                else if(nums[i]+nums[left]+nums[right]<0)
                    left++;
                else{
                    //将结果加入endResult中,这个语句是这样写的。
                    endResult.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //这里就需要去重了
                    while (left<right&&nums[right-1]==nums[right])right--;//假设2,3,3,循环结束后right指的是最后一个重复元素3(第2个)
                    while (left<right&&nums[left+1]==nums[left])left++;//同理
                    right--;//这里才正真跳到最终不同的值上
                    left++;
                }
            }
        }
        return endResult;
    }
}

18.四数之和

题目链接/文章讲解/视频讲解: 代码随想录

在三数之和基础上再套一层循环。

看完代码随想录的想法

剪枝的逻辑不能是nums[i]>0,因为此时目标是target,而target可能是负数,排序之后的数组可以是越加越小,即target = -5, nums = [-4,-1,0,0]。

但是我们依旧可以去做剪枝,逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

 每次对第一个元素不做判断,所以第二层循环去重时j>i+1&&nums[j]==nums[j-1],而不应当惯性思维是j>0

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> endResult = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //剪枝
            if(nums[i]>target&&(nums[i]>0||target>0))
                return endResult;
            if(i>0&&nums[i]==nums[i-1])
                continue;
            for (int j = i + 1; j < nums.length - 1 - 1; j++) { //0,1,2,3,j<2,
                //去重
                if( j > i+1 &&nums[j] == nums [j-1]) //j为1时不应去重
                    continue;
                int left = j+1;
                int right = nums.length-1;
                while (left<right){
                    if(nums[i]+nums[j]+nums[left]+nums[right]>target)right--;
                    else if(nums[i]+nums[j]+nums[left]+nums[right]<target)left++;
                    else{
                        endResult.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++;
                    }
                }
            }
        }
        return endResult;
    }
}

相关推荐

  1. 代码随想算法训练7

    2024-07-10 05:10:36       28 阅读
  2. 代码随想算法训练 | 字符串

    2024-07-10 05:10:36       57 阅读
  3. 代码随想算法训练17

    2024-07-10 05:10:36       57 阅读
  4. 代码随想算法训练16

    2024-07-10 05:10:36       36 阅读
  5. 代码随想算法训练|

    2024-07-10 05:10:36       25 阅读
  6. 代码随想算法训练28|回溯

    2024-07-10 05:10:36       27 阅读
  7. 代码随想算法训练30|回溯

    2024-07-10 05:10:36       29 阅读
  8. 代码随想算法训练25|回溯

    2024-07-10 05:10:36       34 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-10 05:10:36       66 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-10 05:10:36       70 阅读
  3. 在Django里面运行非项目文件

    2024-07-10 05:10:36       57 阅读
  4. Python语言-面向对象

    2024-07-10 05:10:36       68 阅读

热门阅读

  1. 关于美国服务器IP的几个常见问题

    2024-07-10 05:10:36       30 阅读
  2. html&css基础

    2024-07-10 05:10:36       24 阅读
  3. 【云原生】Kubernetes部署高可用平台手册

    2024-07-10 05:10:36       21 阅读
  4. Ubuntu 20.04.6 安装 docker

    2024-07-10 05:10:36       28 阅读
  5. 数据结构第07节:队列

    2024-07-10 05:10:36       25 阅读
  6. 洛谷P2176 [USACO11DEC] RoadBlock S / [USACO14FEB]Roadblock G/S

    2024-07-10 05:10:36       26 阅读
  7. ESP8266 Soft WDT reset

    2024-07-10 05:10:36       30 阅读
  8. Python程序打包成EXE文件指南

    2024-07-10 05:10:36       25 阅读
  9. MongoDB 全文检索

    2024-07-10 05:10:36       22 阅读