当前位置：首页 > article >正文

day-59 四数之和

article 2024/9/25 9:01:31

在这里插入图片描述
思路
双指针：类似16. 最接近的三数之和，将数组排序后，只需要枚举第一个数，则会变为与第16题相似的解题思路

解题过程
枚举选取的第一个数，0<=i<len-3,然后就是第16题的解题思路

Code

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int len=nums.length;
        int m=0;
        int n=0;
        List<List<Integer>> list=new ArrayList<>();
        for(int i=0;i<len-3;i++){
            for(int j=2;j<len-1;j++){
                m=i+1;
                n=len-1;
                while(m<j&&n>j){
                    long num=(long)nums[i]+nums[j]+nums[m]+nums[n];
                    if(num==target){
                        List<Integer> t=new ArrayList<>();
                        t.add(nums[i]);
                        t.add(nums[j]);
                        t.add(nums[m]);
                        t.add(nums[n]);
                        if(!list.contains(t))
                        list.add(t);
                    }
                    if(num<=target) m++;
                    else n--;
                }
            }
        }
        return list;
    }
}

作者：菜卷
链接：https://leetcode.cn/problems/4sum/solutions/2928969/si-shu-zhi-he-by-ashi-jian-chong-dan-lia-rkvp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。