lc454四数相加||

思路

使用map将时间复杂度将至n^2

代码

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num1 : nums1){
            for (int num2 :nums2){
                map.put(num1+num2, map.getOrDefault(num1+num2, 0)+1);
            }
        }
        for (int num3 : nums3){
            for (int num4 : nums4){
                res += map.getOrDefault(-num3-num4, 0);
            }
        }
        return res;
    }
}

lc383赎金信

思路

map的简单应用

代码

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        char[] mag = magazine.toCharArray();
        for (char ch : mag){
            map.put(ch, map.getOrDefault(ch,0)+1);
        }
        char[] rand = ransomNote.toCharArray();
        for (char ch : rand){
            map.put(ch, map.getOrDefault(ch,0)-1);
        }
        for (int item : map.values()){
            if (item < 0){
                return false;
            }
        }
        return true;
    }
}

lc15三数之和

思路

一个循环遍历（确定一个数），双指针确定另外两个数，注意添加成功后的两元素去重和循环遍历中的定元素去重

代码

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

lc18四数之和

思路

三数之和的基础上多加一层循环，注意去重时的条件

代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  // 排序数组
        List<List<Integer>> res = new ArrayList<>();  // 结果集
        for (int k = 0; k < nums.length; k++) {
            if (nums[k] > target && nums[k] >= 0){//非负且大于target，加上就会超
                continue;
            }
            if (k > 0 && nums[k] == nums[k-1]){//nums[k]去重
                continue;
            }
            for (int i = k+1; i < nums.length; i++){
                if (nums[k]+nums[i] > target && nums[k]+nums[i] >= 0){
                    continue;
                }
                if (i > k+1 && nums[i] == nums[i-1]){
                    continue;
                }
                int left = i+1, right = nums.length-1;
                while (left < right){
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target){
                        right--;
                    } else if (sum < target){
                        left++;
                    } else {
                        res.add(Arrays.asList(nums[k], 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 res;
    }
}