leetcode-四数求和（刷题记录）

大佬轻点

给你一个由 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

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

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

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

这题的题目描述上存在歧义，0 <= a, b, c, d < n，a、b、c 和 d 互不相同，但是下面的样例中存在[2，2，2，2，2]，并且解为{[2,2,2,2]},这里我以样例为准，

本题前面的三数求和思路一致，都是使用的双指针方法，减少无用的遍历，降低时间复杂度，这题难点在于去重，一开始我曾使用排序list，Set去重，后面发现这样并不能正确得到结果。最后我在每次遍历时，判断此时指针指向的元素，是否和上一次的指针所指的元素相同（相等），如果相等，则跳过，指针再次偏移，以达到去重的目的。

代码如下：

class Solution {
    public List> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  //对数组进行从小到大排序
        int len = nums.length;
        ArrayList> lists = new ArrayList<>();

        if (len<4)
            return lists;
        for (int first = 0; first < len; first++) {
            if (first>0&&nums[first]==nums[first-1])
                continue;
            for (int second = first+1; second < len; second++) {
                if (second>first+1&&nums[second]==nums[second-1])
                    continue;
                int forth = len-1;//尾指针
                for (int three = second+1; three < len; three++) {
                    if (three>second+1&&nums[three]==nums[three-1])
                        continue;
                    while (threetarget){
                        forth--;
                    }
                    if (three==forth)
                        break;
                    if (nums[first]+nums[second]+nums[three]+nums[forth]==target){
                        ArrayList list = new ArrayList<>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[three]);
                        list.add(nums[forth]);
                        lists.add(list);
                    }
                }
            }
        }
        return lists;
    }
}