LeetCode 四数之和【双指针】【剪枝】

ゝ一世哀愁。 2022-09-10 11:07 128阅读 0赞

# 1 四数之和 #

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

# 2 解题 #

**思路：** 跟3数之和比较类似，2数组合+双指针+剪枝

public List<List<Integer>> fourSum(int[] nums, int target) { 
            //1 排序
            Arrays.sort(nums);
            List<List<Integer>> rs = new ArrayList<>();
            for (int left = 0; left < nums.length - 3; left++) { 
                //防止重复
                if (left > 0 && nums[left] == nums[left - 1]) { 
                    continue;
                }
                //最大值小于target left left 右移
                if (nums[left] + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) { 
                    continue;
                }
                //最小值大于target 直接break
                if (nums[left] + nums[left + 1] + nums[left + 2] + nums[left + 3] > target) { 
                    break;
                }
    
                //2 组合
                for (int right = left + 1; right < nums.length - 2; right++) { 
    
                    if (right > left + 1 && nums[right] == nums[right - 1]) { 
                        continue;
                    }
                    //最小值大于target 直接break
                    if (nums[left] + nums[right] + nums[right + 1] + nums[right + 2] > target) { 
                        break;
                    }
                    //最大值小于target continue
                    if (nums[left] + nums[right] + nums[nums.length - 1] + nums[nums.length - 2] < target) { 
                        continue;
                    }
                    int leftChild = right + 1;
                    int rightChild = nums.length - 1;
                    //双指针
                    while (leftChild < rightChild) { 
                        int sum = nums[left] + nums[right] + nums[leftChild] + nums[rightChild];
                        if (sum > target) { 
                            rightChild--;
                        } else if (sum < target) { 
                            leftChild++;
                        } else { 
                            //添加
                            rs.add(Arrays.asList(nums[left], nums[leftChild], nums[rightChild], nums[right]));
                            //防止重复
                            while (leftChild < rightChild && nums[++leftChild] == nums[leftChild - 1]) ;
                            while (leftChild < rightChild && nums[--rightChild] == nums[rightChild + 1]) ;
                        }
                    }
                }
    
            }
            return rs;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/fd2129a66f2b48378167bb026be69c77.png