LeetCode-18.四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解题思路：

先将数组排序，四个数的下标分别用first、second、third、last 表示，使用三层循环

LeetCode-18.四数之和

为避免重复计算和排出相同的四元组，first、second、third、last移动时，不逐步移动，一直判断到下一元素的值与上一次循环对应的值不同时，才进行后续判断查找符合条件的四元组

代码：

public static List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new LinkedList<>();

    int len = nums.length;
    if(len < 4)
        return result;

    //排序
    Arrays.sort(nums);

    for(int first = 0; first < len; first++){
        //避免相同元素重复计算
        while(first > 0 && first < len-1 && nums[first] == nums[first-1])
            first++;

        for(int last = len-1; last > first; last--){
            //避免相同元素重复计算
            while(last < len-1 && last >= 0 && nums[last] == nums[last+1])
                last--;
            int second = first + 1;
            int third = last - 1;
            while(second < third){
                int sum = nums[first] + nums[second] + nums[third] + nums[last];
                if(sum > target){
                    third--;
                    //避免相同元素重复计算
                    for(; third > second && nums[third] == nums[third+1]; third--);
                }
                else if(sum < target){
                    second++;
                    //避免相同元素重复计算
                    for(; second < third && nums[second] == nums[second-1]; second++);
                }
                else {
                    List<Integer> re = new ArrayList<>(4);
                    re.add(nums[first]);
                    re.add(nums[second]);
                    re.add(nums[third]);
                    re.add(nums[last]);
                    result.add(re);

                    second++;
                    //避免相同元素重复计算
                    while(second < third && nums[second] == nums[second-1])
                        second++;
                }
            }
        }
    }

    return result;
}

该解法效率有限，可寻找更高效的解法

LeetCode-18.四数之和

相关推荐