Day06

今日任务

• 454 四数相加II
• 383 赎金信
• 15 三数之和
• 18 四数之和

---

454?四数相加II

题目链接：https://leetcode.cn/problems/4sum-ii/description/

?关键：分组遍历（降低时间复杂度） + 哈希表（提供查找效率）

思路：

1. 先遍历前两个数，然后将其和及对应出现的次数存放在哈希表
2. 再遍历后两个数的和，当两边正好相反的时候，就是和为0的时候
3. 将和为0的遍历后加起来就是一共组合的数目

代码：

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

---

383 赎金信

题目链接：https://leetcode.cn/problems/ransom-note/description/

典型的哈希表问题，可以使用数组解决

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for(char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for(char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

---

15 三数之和

题目链接：https://leetcode.cn/problems/3sum/description/

关键：如何处理不可包含重复元素?

思路：?

1. 先对数组进行排序，如果第一个就大于0，那么就不存在成立的
2. 第一个定为 i，然后右边为 left 指针，最右边为 right 指针
3. 三数之和 如果 大于0，那么right 就向左移动
4. 三数之和 如果 小于0，那么left 就向右移动
5. 如果等于 0 ，就需要同时移动两个指针，并且还要注意去重

代码：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        int len = nums.length;
        if(nums == null || len < 3) {
            return res;
        }
        //数组排序
        Arrays.sort(nums);
        //遍历数组中的每一个元素
        for(int i = 0; i < len; i++) {
            if(nums[i] > 0) {
                break;
            }
            //去重 当起始的值等于前一个元素，那么得到的结果将会和前一次相同
            if(i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            //双指针开始
            int left = i + 1;
            int right = len - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[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){
                    while(left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    left++;
                }else if(sum > 0) {
                    while(left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    right--;
                }
            }
        }
        return res;
    }
}

---

18 四数之和

题目链接：https://leetcode.cn/problems/4sum/description/

?思路是和上一题是一样的，就是多加了一层循环

代码：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();

        Arrays.sort(nums);
        int len = nums.length;
        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 (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;

                }
                int left = j + 1;
                int right = len - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList
                            (nums[i],nums[j],nums[left],nums[right]));
                        while (left < right && nums[left + 1] == nums[left])
                            left++;
                        while (left < right && nums[right - 1] == nums[right])
                            right--;
                        left++;
                        right--;
                    } else if (sum > target) {
                        right--;
                    } else {
                        left++;
                    }
                }
            }
        }

        return res;
    }
}