LeetCode 4Sum 数组中多数求和等于目标值

╰+哭是因爲堅強的太久メ 2021-06-24 16:10 406阅读 0赞

**试题：**  
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = \[1, 0, -1, 0, -2, 2\], and target = 0.

A solution set is:  
\[  
\[-1, 0, 0, 1\],  
\[-2, -1, 1, 2\],  
\[-2, 0, 0, 2\]  
\]  
**代码：**

class Solution {
        List<List<Integer>> out = new ArrayList<List<Integer>>();
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            findNsum(nums, 0, nums.length-1, target, 4, new ArrayList<Integer>());
            return out;
        }
        public void findNsum(int[] nums, int l, int r, int target, int N, ArrayList<Integer> tem){
            if(r-l+1<N || target<nums[l]*N ||target>nums[r]*N) return;
            if(N==2){
                while(l<r){
                    int sum = nums[l] + nums[r];
                    if(target<sum){
                        r--;
                    }else if(target>sum){
                        l++;
                    }else{
                        ArrayList<Integer> ooo = (ArrayList<Integer>)tem.clone();
                        ooo.add(nums[l]);
                        ooo.add(nums[r]);
                        this.out.add(ooo);
                        l++;
                        while(l<r && nums[l]==nums[l-1]) l++;
                    }
                }
            }else{
                for(int i=l; i<=r; i++){
                    if(i==l || (i>l && nums[i-1]!=nums[i])){
                        ArrayList<Integer> newtem = (ArrayList<Integer>)tem.clone();
                        newtem.add(nums[i]);
                        findNsum(nums, i+1, r, target-nums[i], N-1, newtem);
                    }
                }
            }
        }
    }