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

今日任务

● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ● 18. 四数之和 ● 总结

链接：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj (opens in a new tab)

454.四数相加II

题解想法

本题是四个独立的数组，而且不考虑去重，因此较为简单，用哈希法两两成组遍历，复杂度O(n^2)。

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

383. 赎金信

自己想法

类似：242.有效的字母异位词

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

15. 三数之和

自己想法

哈希没做出来。。

题解想法

本题是要拿到数值本身，而不是问答案的个数；同时是从一个数组里取数还要考虑不能重复拿；以及拿出来的三元组要去重。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 这一层for复杂度O(n)
            if (i > 0 && nums[i] == nums[i - 1]) {
                // 去重nums[i]
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                // 这一层while复杂度O(n)
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left ++;
                }
                else if (sum > 0) {
                    right --;
                }
                else {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重nums[left],nums[right]
                    while (left < right && nums[left + 1] == nums[left]) left ++;
                    while (left < right && nums[right - 1] == nums[right]) right --;
                    left ++;
                    right --;
                }
            }
        }
        return ans;
    }
}

回顾

解法：双指针，注意去重位置
Array相关方法：new ArrayList<>(), Arrays.sort(), Arrays.asList()。

18. 四数之和

自己想法（沿用上题题解想法）

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    // int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) left ++;
                    else if (sum > target) right --;
                    else {
                        ans.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 --;
                    }
                }
            }
        }
        return ans;
    }
}