No.1

题目

四数相加 II

思路

• 很妙的办法：有四个数组A、B、C、D，用hashMap记录【A、B中数字之和】+【这些和出现的次数】，再遍历C、D中数字组合，寻找【0-C、D中数字之和】在hashMap中出现的次数，并累加
• 本质上，这是把4个数组简化成了2个数组

代码

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {  
    // 记录A、B中元素之和+出现次数  
    Map<Integer, Integer> ABhash = new HashMap<>();  
    int targetCount = 0;  
  
    for (int i = 0; i < nums1.length; i++) {  
        for (int j = 0; j < nums2.length; j++) {  
            // 取出“和”+1，统计“和”出现次数  
            ABhash.put(nums1[i] + nums2[j], ABhash.getOrDefault(nums1[i] + nums2[j], 0) + 1);  
        }  
    }  
  
    for (int i = 0; i < nums3.length; i++) {  
        for (int j = 0; j < nums4.length; j++) {  
            if (ABhash.containsKey(-nums3[i] - nums4[j]))  
                targetCount += ABhash.get(-nums3[i] - nums4[j]);  
        }  
    }  
  
    return targetCount;  
}

No.2

题目

赎金信

思路

• 用一个int[]记录magazine中字母出现次数
• 遍历ransomNote，消耗可用字母数
• 出现负值，就是不够用，可以返回false

代码

public boolean canConstruct(String ransomNote, String magazine) {  
    // 记录26个字母的出现次数  
    int[] alphabet = new int[26];  
  
    // 统计可用字母数量  
    for (int i = 0; i < magazine.length(); i++) {  
        char item = magazine.charAt(i);  
        alphabet[item - 'a']++;  
    }  
  
    // 消耗字母  
    for (int i = 0; i < ransomNote.length(); i++) {  
        char item = ransomNote.charAt(i);  
        // 不够用，false  
        if (--alphabet[item - 'a'] < 0)  
            return false;  
    }  
  
    return true;  
}

No.3

题目

三数之和

思路

• 先升序排序，因为有序的数组，相同的数字一定靠在一起，这样就可以跳过重复的数字，从而去重
• 升序排序后，第一个数字大于target，就不用找了，返回空数组
• 升序排序后，最后一个数字小于target，就不用找了，返回空数组
• 双指针法
• 对数字a、b、c都要去重
• 参看去重逻辑的思考

代码

public List<List<Integer>> threeSum(int[] nums) {  
    List<List<Integer>> result = new ArrayList<>(); // 存结果  
    Arrays.sort(nums); // 先排序  
  
    // 升序数组，最小元素大于0或者最大元素小于0，都没有必要再找了  
    if (nums[0] > 0 || nums[nums.length - 1] < 0)  
        return result;  
  
    for (int i = 0; i < nums.length - 2; i++) {  
        // 去重  
        if (i > 0 && nums[i] == nums[i - 1])  
            continue;  
        int left = i + 1, right = nums.length - 1;  
        while (left < right) {  
            int sum = nums[i] + nums[left] + nums[right];  
            if (sum < 0) {  
                left++;  
            } else if (sum > 0) {  
                right--;  
            } else {  
                result.add(new ArrayList<>(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--;  
            }  
        }  
    }  
  
    return result;  
}

No.4

题目

四数之和

思路

• 相比三数之和，和从0变成了target，思路还是类似
• 去重的细节要特别注意
• 需要仔细考虑双指针去重逻辑

代码

public List<List<Integer>> fourSum(int[] nums, int target) {  
    Arrays.sort(nums); // 排序  
    List<List<Integer>> result = new ArrayList<>(); // 存结果  
  
    // 最小的数字大于target，不能找到和为target的数  
    if (nums[0] > target)  
        return result;  
  
    for (int i = 0; i < nums.length - 3; i++) {  
        // 剪枝，访问过nums[0]之后再判重  
        if (i > 0 && nums[i] == nums[i - 1]) continue;  
        for (int j = i + 1; j < nums.length - 2; j++) {  
            // 剪枝，访问过nums[i+1]之后再判重  
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;  
            int left = j + 1, right = nums.length - 1;  
  
            while (left < right) {  
                int sum = nums[i] + nums[j] + nums[left] + nums[right];  
                if (sum > target) right--;  
                else if (sum < target) left++;  
                else {  
                    result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));  
                    // 去重  
                    while (left < right && nums[left] == nums[left + 1]) left++;  
                    while (left < right && nums[right] == nums[right - 1]) right--;  
  
                    right--;  
                    left++;  
                }  
            }  
        }  
    }  
  
    return result;  
}