题目链接

题目:

分析:

• 我们已经知道三数之和如何求取, 并去重了  三数之和 
• 那么四数之和同理, 需要固定两个数a和b 然后用"双指针算法" , 只要两指针之和等于target-a-b即可
• 同样对于四个数都要进行去重

代码:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int a = 0;
        int n = nums.length;
        while (a < n-3) {
            int b = a + 1;
            while (b < n-2) {
                int left = b + 1;
                int right = n - 1;
                long t1 = (long)target - nums[a] - nums[b];
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum > t1) {
                        right--;
                    } else if (sum < t1) {
                        left++;
                    } else {
                        list.add(Arrays.asList(nums[a], nums[b], nums[left], nums[right]));
                        left++;
                        right--;
                        while (nums[left] == nums[left - 1] && left < right) {
                            left++;
                        }
                        while (nums[right] == nums[right + 1] && left < right) {
                            right--;
                        }
                    }
                }
                b++;
                while (nums[b] == nums[b - 1] && b < n-2) {
                    b++;
                }
            }
            a++;
            while (nums[a] == nums[a - 1] && a < n-3) {
                a++;
            }
        }
        return list;
    }
}