[数据结构与算法]四数之和 双指针+排序

四数之和

挑战程序设计竞赛 抽签
LeetCode18：四个数之和
知识点：双指针+排序

相关题目
LeetCode18：四个数之和
LeetCode15：三个数之和

• 题目描述：

给你一个由 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
你可以按 任意顺序 返回答案 。

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

• 思路：

  最容易想到的是暴力枚举，四层for循环，但是有一个问题是如何才能满足 不重复的四元组 的条件，例如题目所给的例子中，如果忽略这个条件很容易得到答案

  [[2,2,2,2],[2,2,2,2]]

  一种想法是让每一层for循环遍历的元素各不相同，也就是说第一次遍历到2后，之后再遇到2就直接跳过！在实现上可以利用Set集合去重，但是空间花费太大。

  想要解决去重问题，其实可以通过先排序（例如：从小到大），这样相同的元素就连续的排列着，可以利用下面2条语句去重

  if(first >0&&nums[first] == nums[first-1])
  continue;

  因为已经排过序，所以相同元素都挨着，所以如果遍历到的元素在上一次已经出现过，则直接跳过。
  同时可以利用双指针优化最后一层循环，在已知前3个数的情况下，将第四个数从后向前遍历，只要大于target就前移，在结束循环后判断是否满足条件即可。

public class chouqian {
    //挑战程序设计竞赛 抽签
    //四个数之和为m
    private List<List<Integer>> ans = new LinkedList<>();
    public List<List<Integer>> solve(int[] nums,int target){
        /*
        排序+双指针
         */
        int n=nums.length;
        Arrays.sort(nums);
        for(int first = 0;first < n;first++){
            if(first >0&&nums[first] == nums[first-1])
                continue;
            for(int second=first+1;second<n;second++){
                if(second>first+1&&nums[second]==nums[second-1]){
                    continue;
                }
                int third=n-1;
                int m=target-nums[first]-nums[second];
                for(int three=second+1;three<n;three++){
                    if(three>second+1&&nums[three]==nums[three-1]){
                        continue;
                    }
                    while(three<third&&nums[three]+nums[third]>m){
                        third--;
                    }
                    if(three==third){
                        break;
                    }
                    if(nums[three]+nums[third]==m){
                        List<Integer> one =new LinkedList<>();
                        one.add(nums[first]);
                        one.add(nums[second]);
                        one.add(nums[three]);
                        one.add(nums[third]);
                        ans.add(one);
                    }
                }
            }
        }
        return ans;

    }
}