当前位置:   article > 正文

力扣爆刷第138天之哈希表五连刷(二三四数之和)

力扣爆刷第138天之哈希表五连刷(二三四数之和)

力扣爆刷第138天之哈希表五连刷(二三四数之和)

一、1. 两数之和

题目链接:https://leetcode.cn/problems/two-sum/description/
思路:求两数之和,只需要借用哈希表存放结果与当前值的差值。如果发现当前元素已经存在哈希表中,说明另一个数已经存在了。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])) return new int[] {map.get(nums[i]), i};
            map.put(target - nums[i], i);
        }
        return new int[] {-1, -1};
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

二、454. 四数相加 II

题目链接:https://leetcode.cn/problems/4sum-ii/description/
思路:四数之和可以转化为两数之和,然后按照两数之和的做法来做。先把两个数组的值的匹配和出现的次数统计到map中,然后再利用0 - (c + d),去map中寻找,找到即累加。

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums1.length; i++) {
            for(int j = 0; j < nums2.length; j++) {
                int t = nums1[i] + nums2[j];
                map.put(t, map.getOrDefault(t, 0) + 1);
            }
        }
        for(int i = 0; i < nums3.length; i++) {
            for(int j = 0; j < nums4.length; j++) {
                count += map.getOrDefault(- nums3[i] - nums4[j], 0);
            }
        }
        return count;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

三、383. 赎金信

题目链接:https://leetcode.cn/problems/ransom-note/description/
思路:题目求的是一个字符串是否可以由另一个字符串组成,只需要把第一个字符串用数组(长度26表示26个字母)收集起来,然后遍历另一个数组来判断是否可以组成。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] flag = new int[26];
        for(int i = 0; i < ransomNote.length(); i++) {
            int t = ransomNote.charAt(i) - 'a';
            flag[t]++;
        }
        for(int i = 0; i < magazine.length(); i++) {
            int t = magazine.charAt(i) - 'a';
            if(flag[t] > 0) {
                flag[t]--;
            }
        }
        for(int i : flag) {
            if(i > 0) return false;
        }
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

四、15. 三数之和

题目链接:https://leetcode.cn/problems/3sum/description/
思路:使用两次for循环,三个指针,外层控制一个指针,内存控制两个指针,每层都需要考虑如何去重。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for(int i = 0; i < len-2; i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int j = i+1, k = len - 1;
            while(j < k) {
                int t = nums[i] + nums[j] + nums[k];
                if(t == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    result.add(list);
                    while(j < k && nums[j] == nums[j+1]) j++;
                    while(j < k && nums[k] == nums[k-1]) k--;
                    j++;
                    k--;
                }else if(t < 0) {
                    j++;
                }else{
                    k--;
                }
            }
        }
        return result;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

五、18. 四数之和

题目链接:https://leetcode.cn/problems/4sum/description/
思路:四数之和和三数之和类似,就是多了一层for循环。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int len = nums.length;
        Arrays.sort(nums);
        for(int i = 0; i < len - 3; i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue;
            for(int j = i + 1; j < len - 2; j++) {
                if(nums[i] + nums[j] > target && nums[i] > 0) break;
                if(j > i+1 && nums[j] == nums[j-1]) continue;
                int k = j + 1, h = len - 1;
                while(k < h) {
                    long t =(long) (nums[i] + nums[j] + nums[k] + nums[h]);
                    if(t == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[h]));
                        while(k < h && nums[k] == nums[k+1]) k++;
                        while(k < h && nums[h] == nums[h-1]) h--;
                        k++;
                        h--;
                    }else if (t > target) {
                        h--;
                    }else{
                        k++;
                    }
                }
            }
        }
        return result;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小惠珠哦/article/detail/737849
推荐阅读
相关标签
  

闽ICP备14008679号