[LeetCode]4 Sum,解題報告

前言
明日はもうすぐ帰京して、やはりとても紧张して、今日やはり坚持してテーマをして、androidを见て、晩に荷物を片付けて、言わざるを得なくて、家はやはりとても心地良くて、特に新しい家を引っ越した后で、私はまだ自分の书斎があって、楽しいです
写真をアップロードして、記念して、ああ、ブログの書くのはますます勝手になりました
タイトル
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.
考え方1
最初はとても简単に考えて、すべての组み合わせを要求するため、第1反応はDFSでこの问题を解决することで、仕方がありません
TLEですが、DFSのコードを貼って、参考にしてもらえますし、改善してもらえます.

public class Solution {
    public static ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length < 4) {
            return res;
        }

        Arrays.sort(num);
        
        ArrayList<Integer> tmpStore = new ArrayList<Integer>();

        depthFS(0, 0, 0, num, target, tmpStore, res);

        return res;
    }

    public static void depthFS(int pos, int count, int sum, int[] num, int target,
            ArrayList<Integer> tmpStore, ArrayList<ArrayList<Integer>> res) {
        if (count == 4) {
            if (sum == target) {
                res.add(new ArrayList<Integer>(tmpStore));
            }
        } else {
            for (int i = pos; i < num.length && count < 4; i++) {
                if (sum + num[i] <= target) {
                    tmpStore.add(num[i]);
                    depthFS(i + 1, count + 1, sum + num[i], num, target, tmpStore, res);
                    tmpStore.remove(tmpStore.size() - 1);
                }
            }
        }
    }
}

考え方2
この問題は実は直接3つのforサイクルで解決することができます

public class Solution {
    public static ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length < 4) {
            return res;
        }

        Arrays.sort(num);
        
        HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();
        
        for (int i = 0; i <= num.length - 4; i ++) {
            for (int j = i + 1; j <= num.length - 3; j ++) {
                for (int k = j + 1, h = num.length - 1; k < h;) {
                    int sum = num[i] + num[j] + num[k] + num[h];
                    
                    if (sum < target) {
                        k ++;
                        continue;
                    }
                    
                    if (sum > target) {
                        h --;
                        continue;
                    }
                    
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(num[i]);
                    tmp.add(num[j]);
                    tmp.add(num[k]);
                    tmp.add(num[h]);
                    
                    if (! hashSet.contains(tmp)) {
                        hashSet.add(tmp);
                        res.add(tmp);
                    }
                    
                    k ++;
                    h --;
                }
            }
        }
        
        return res;
    }
}

後記
なぜこの問題を記録するのかというと、考え方1のDFSが失敗した後、私は無意識にこれがすごいテーマだと思っていたので、ダイナミックな計画+枝切りを使う必要があるかどうか、私は興味津々に考え1を書いてから考え始めました.
途中で前にダブルポインタacのTwo sum問題を見て、この問題も3つのforループで解決できるかどうかを考えて、お父さん、本当にできるので、このブログを書きました.