【LeetCode专题】最接近的三数之和 穷举+双指针 四数之和 穷举+双指针

最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

暴力解法 穷举+间隔判断

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans=nums[0]+nums[1]+nums[2];
        if(target<=ans)
        {
            return ans;
        }
        for(int i=0;iMath.abs(target-sum))//这里一定要大于才可以，不然会存在bug,因为，如果target=1,ans=-1,sum=1,这里会存在bug
                    {
                        ans=sum;
                    }
                }
            }
        }
        return ans;
    }
}

方法二：双指针

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int res=nums[0]+nums[1]+nums[2];
        for(int i=0;itarget)
                {
                    r--;
                }else if(sum 
四数之和
 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 0 <= a, b, c, d < n
 a、b、c 和 d 互不相同
 nums[a] + nums[b] + nums[c] + nums[d] == target
 你可以按 任意顺序 返回答案 。
 穷举+去重
 代码如下：
 
class Solution {
    public List> fourSum(int[] nums, int target) {
        Arrays.sort(nums);//排序为去重做铺垫
        List> lists=new ArrayList<>();
        
        for(int i=0;i0 && nums[i-1]==nums[i])//去重
            {
                continue;
            }
            for(int j=i+1;ji+1 && nums[j-1]==nums[j])//去重
                {
                continue;
                }
                for(int k=j+1;kj+1 && nums[k-1]==nums[k])//去重
                    {
                        continue;
                    }
                    for(int z=k+1;z list=new ArrayList<>();
                        if(nums[i]+nums[j]+nums[k]+nums[z]==target)
                        {
                            list.add(nums[i]);
                            list.add(nums[j]);
                            list.add(nums[k]);
                            list.add(nums[z]);
                            if(!lists.contains(list))
                            {
                               lists.add(list);  
                            }
                            
                        }
                    }
                }
            }
        }

        return lists;
    }
}
 
双指针法：
 
class Solution {
    public List> fourSum(int[] nums, int target) {
        List> res=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i0 && nums[i]==nums[i-1])
            {
                continue;
            }
            for(int j=i+1;ji+1 && nums[j]==nums[j-1])
                {
                    continue;
                }
                int left=j+1,right=nums.length-1;
                while(lefttarget)
                    {
                        right--;
                    }
                    else if(sumleft && nums[right]==nums[right-1]) right--;
                        while(right>left && nums[left]==nums[left+1]) left++;
                        left++;
                        right--;
                    }
                }
            }



        }
        return res;

    }
}