LeetCode：四数相加（四个数组）、四数之和（一个数组）

爱被打了一巴掌 2021-12-20 10:49 256阅读 0赞

public class Solution_454 {
        /**
         * 四数相加：
         * 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
         * 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，
         * 最终结果不会超过 231 - 1 。
         */
        public static int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < A.length; i++) {
                for (int j = 0; j < B.length; j++) {
                    int key = A[i] + B[j];
                    if (map.containsKey(key)) {
                        map.put(key, map.get(key) + 1);
                    } else {
                        map.put(key, 1);
                    }
                }
            }
    
            int res = 0;
            for (int i = 0; i < C.length; i++) {
                for (int j = 0; j < D.length; j++) {
                    // 因为结果是4数相加得0，所以通过0-(C[i] + D[j])，对(C[i] + D[j])取反
                    // 然后选择map里面存等于(C[i] + D[j])的值
                    int key = 0 - C[i] - D[j];
                    if (map.containsKey(key)) {
                        res += map.get(key);
                    }
                }
            }
            return res;
    
        }
    
        /**
         * 四数之和
         * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，
         * 判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
         * <p>
         * 注意：答案中不可以包含重复的四元组，所以不能按照四数相加通过Map去得到结果
         */
        public static List<List<Integer>> fourSum(int[] numbers, int target) {
            Arrays.sort(numbers);
            List<List<Integer>> ret = new ArrayList<>();
            dfs(ret, new ArrayList<Integer>(), numbers, 0, target);
            return ret;
        }
    
        private static void dfs(List<List<Integer>> ret, ArrayList<Integer> condidate, int[] numbers, int curIndex,
                                int target) {
            // 以后求n数和，只要改这里就能解决，比如4改为3，改为5
            if (condidate.size() == 4) {
                int total = getSum(condidate);
                if (total == target) {
                    ret.add(new ArrayList<>(condidate));
                }
                return;
            }
            if (curIndex > numbers.length - 1) {
                return;
            }
            for (int i = curIndex; i < numbers.length; i++) {
                // 如果是一样的数字，直接忽略，否则会有重复的答案
                if (i != curIndex && numbers[i] == numbers[i - 1]) {
                    continue;
                }
                condidate.add(numbers[i]);
                // 如果已经大于target，并且当前数字大于0，再循环加下去已经没有意义了，因为只会更大，直接return
                if (getSum(condidate) > target && numbers[i] > 0) {
                    if (!condidate.isEmpty()) {
                        condidate.remove(condidate.size() - 1);
                    }
                    return;
                }
                dfs(ret, condidate, numbers, i + 1, target);
    
                if (!condidate.isEmpty()) {
                    condidate.remove(condidate.size() - 1);
                }
            }
        }
    
        private static int getSum(ArrayList<Integer> condidate) {
            int total = 0;
            for (Integer num : condidate) {
                total += num;
            }
            return total;
        }
    
    
        public static void main(String[] args) {
            /*int[] A = {1, 2}, B = {-2, -1}, C = {-1, 2}, D = {0, 2};
            System.out.println(fourSumCount(A, B, C, D));*/
    
            int[] nums = {1, 0, -1, 0, -2, 2};
            int target = 0;
            System.out.println(fourSum(nums, target));
        }
    
    }