首页 > 代码库 > 【LeetCode】4Sum

【LeetCode】4Sum

2024-07-05 16:25:23   230人阅读

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

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • The solution set must not contain duplicate quadruplets.

 

    For example, given array S = {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)
public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> re = new ArrayList<ArrayList<Integer>>();
        Map<ArrayList<Integer>,Integer> map = new HashMap<ArrayList<Integer>,Integer>();
        ArrayList<Integer> ai = new ArrayList<Integer>();
        if(num.length<=3)
            return re;
        Arrays.sort(num);
        for(int i=0;i<num.length-3;i++){
            
            ai = new ArrayList<Integer>();
            ai.add(num[i]);
            int tar = target-num[i];
            for(int j=i+1;j<num.length-2;j++){
                int temp = num[j];
                ai = new ArrayList<Integer>();
                ai.add(num[i]);
                ai.add(temp);
                int tt = tar-temp;
                int start = j+1;
                int end = num.length-1;
                while(end>start){
                    if(num[start]+num[end]==tt){
                        ai.add(num[start]);
                        ai.add(num[end]);
                        map.put(ai, 1);
                        ai=new ArrayList<Integer>();
                        ai.add(num[i]);
                        ai.add(temp);
                        start++;
                        end--;
                        continue;
                    }
                    if(num[start]+num[end]>tt){
                        end--;
                        continue;
                    }
                    if(num[start]+num[end]<tt){
                        start++;
                        continue;
                    }
                }
            }
            
        }
        re.addAll(map.keySet());
        return re;
        
    }
}

 


联系
我们