题解 | #牛群的标签和#

题目考察的知识点

考察双指针算法

题目解答方法的文字分析

数组排序后，使用双指针遍历，左右指针分别从前后遍历。双重遍历查找符合要求的四个数的组合。注意去重，细节参看代码实现即可。

本题解析所用的编程语言

使用Java解答

完整且正确的编程代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型二维数组
     */
    public int[][] fourSum (int[] nums, int target) {
        // write code here
        List<List<Integer>> res = new ArrayList();
        Arrays.sort(nums);
        for(int i=0; i<nums.length-3; i++){
            if(i>0&&nums[i]==nums[i-1]) continue; // 去重
            for(int j=i+1;j<nums.length-2; j++){
                // 同样去重
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                int left = j+1,right = nums.length-1;
                while(left<right){
                    //int tag = target - nums[i] - nums[j];
                    if((long)nums[left] + nums[right] + nums[i] + nums[j] >target){
                        right--;
                    }else if((long)nums[left]+nums[right]+nums[i] + nums[j]<target){
                        left++;
                    }else{
                        ArrayList<Integer> temp = new ArrayList<>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[left]);
                        temp.add(nums[right]);
                        res.add(new ArrayList(temp));
                        while(left<right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        while(left<right&&nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        if(res.size()==0) return new int[][]{};
        int[][] ret = new int[res.size()][res.get(0).size()];
        for(int i=0; i<res.size(); i++){
            for(int j=0; j<res.get(0).size(); j++){
                ret[i][j] = res.get(i).get(j);
            }
        }
        return ret;
    }
}