四数相加

题目链接

https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

思路

hash法，两两数组相加，统计和出现的次数

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

赎金信

题目链接

https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

思路

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

三数之和

题目链接

https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

思路

对结果需要去重，且不需要记录元素位置，故可以先对数组排序，然后使用双指针法，本题目难度在于如何去重

    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    for(int i = 0; i < nums.length - 2;i++) {
        //避免-1 -1 2被漏掉
        if(i > 0 && nums[i] == nums[i -1]) {
            continue;
        }
        int left = i + 1;
        int right = nums.length - 1;
        while(left < right) {
            if(nums[left] + nums[right] + nums[i] > 0) {
                right--;
            } else if (nums[left] + nums[right] + nums[i] < 0) {
                left++;
            } else {
                list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while(right > left && nums[right] == nums[right - 1]) {
                    right--;
                }
                while (right>left && nums[left]==nums[left+1]) {
                    left++;
                }
                right--;
                left++;
            }
        }
    }
    return list;
}

四数之和

题目链接

https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html

思路

和三数之和一样，外面套一层循环

    public List<List<Integer>> fourSum(int[] nums, int target) {

Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i < nums.length;i++) {
if(nums[i] > target && nums[i] >= 0 ) {
break;
}

        if(i > 0 && nums[i]== nums[i-1]) {
            continue;
        }
        
        for(int k = i + 1; k < nums.length;k++) {

            if(nums[k] + nums[i] > target && nums[k] + nums[i] >=0) {
                break;
            }
                if(k > i +1 && nums[k] == nums[k-1]) {
                    continue;
                }
            
            int left = k + 1;
            int right = nums.length - 1;
            while(left < right) {
                if((long)nums[left]+ nums[right] + nums[k] + nums[i] > target) {
                    right--;
                } else if ((long)nums[left]+ nums[right] + nums[k] + nums[i] < target) {
                    left++;
                } else {
                    list.add(Arrays.asList(nums[i], nums[left], nums[right],nums[k]));
                    while(right > left && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    while (right>left && nums[left]==nums[left+1]) {
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
    }
    return list;
}