nSum问题

nSum问题选编

15. 3Sum

注意：

1. 只求值，不求坐标，可以排序！
2. 用左右双指针
3. 考虑去重
   • for 循环中
   • while 循环中

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();
        int n=nums.length;
        for(int i=0; i<n; i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=n-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<n-1 && nums[left]==nums[left+1]){
                        left++;
                    }
                    left++;
                    while(right>0 && nums[right]==nums[right-1]){
                        right--;
                    }
                    right--;
                }else if(sum>0){
                    while(right>0 && nums[right]==nums[right-1]){
                        right--;
                    }
                    right--;
                }else{
                    while(left<n-1 && nums[left]==nums[left+1]){
                        left++;
                    }
                    left++;
                }
            }
        }
        return res;
    }
}

16. 3Sum Closest

注意：

1. 依然以 sum 为判断条件，分别考虑 sum 等于、大于、小于target时的情况

public class LeetCode16 {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n=nums.length;
        int curSum=Integer.MAX_VALUE;
        int cur=Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=n-1;
            while(left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum==target){
                    cur=0;
                    curSum=sum;
                    break;
                }else if(sum>target){
                    if(sum-target<cur){
                        cur=sum-target;
                        curSum=sum;
                    }
                    while(right>0 && nums[right]==nums[right-1]){
                        right--;
                    }
                    right--;
                }else{
                    if(target-sum<cur){
                        cur=target-sum;
                        curSum=sum;
                    }
                    while(left<n-1 && nums[left]==nums[left+1]){
                        left++;
                    }
                    left++;
                }
            }
        }
        return curSum;
    }
}

18. 4Sum

注意去重：

1. 外层 for 去重逻辑不变，跳过重复的第一个元素
2. 内层 for 去重逻辑：跳过重复的第二个元素

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

259. 3Sum Smaller

注意：

1. 以 left 为计数基准， 找到符合条件的组合后就更新 left， 避免重复

public class LeetCode259 {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int count=0;
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            int left=i+1;
            int right=n-1;
            while(left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum<target){
                    count+=right-left;
                    left++;
                }else if(sum>=target){
                    right--;
                }
            }
        }
        return count;
    }
}

454. 4Sum II

注意：

1. 只要求 count, 无需求值，则考虑用 HashMap 记录前两个数组各 sum 出现的次数
2. 遍历后两个数组，考察 0-sum 的数量

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

653. Two Sum IV - Input is a BST

public boolean findTarget(TreeNode root, int k) {
    Set<Integer> set=new HashSet<>();
    Deque<TreeNode> q=new LinkedList<>();
    q.offer(root);
    while(!q.isEmpty()){
        TreeNode cur=q.poll();
        int val=cur.val;
        if(set.contains(k-val)){
            return true;
        }
        set.add(val);
        if(cur.left!=null){
            q.offer(cur.left);
        }
        if(cur.right!=null){
            q.offer(cur.right);
        }
    }
    return false;
}

1214. Two Sum BSTs

dfs很慢

public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
    if(root1==null || root2==null){
        return false;
    }
    int sum=root1.val+root2.val;
    if(sum==target){
        return true;
    }
    if(sum<target){
        return twoSumBSTs(root1.right,root2,target) || twoSumBSTs(root1,root2.right,target);
    }else{
        return twoSumBSTs(root1.left,root2,target) || twoSumBSTs(root1,root2.left,target);
    }
}