代码随想录05

LeetCode454  四数相加

给定四个包含整数的数组列表 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 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

例如:

输入:

• A = [ 1, 2]
• B = [-2,-1]
• C = [-1, 2]
• D = [ 0, 2]

输出:

2

解释:

两个元组如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0  = 0

思路：

找出存在的结果，存在性问题，想到使用哈希表去解决。本题找四个值加起来等于0。解法类似于两数之和那一题，

那一题是判断两数之和等于指定值，判断目标值减一个数是否存在。本题也可以这么做。四个数，我们可以拆成两个一组

这样可以保证时间复杂度平分，变成n^2,如果是三个一组和一个一组进行比较，时间复杂度取得是n^3。我们这题是求出现的次数

所以还需要一个值来存次数，想到可以使用map，key存两数之和进行目标值比对，value存出现次数用来统计。

代码：

package com.dwj.LeetCode.HashList;

import java.util.HashMap;
import java.util.Map;

/**
 * 四数相加
 * 判断四数相加等于0出现的次数
 */
public class FourNumberPlus {
    class Solution {
        public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
            Map<Integer, Integer> map = new HashMap<>();
            int temp;
            int res = 0;
            //统计两个数组中的元素之和，同时统计出现的次数，放入map
            for (int i : nums1) {
                for (int j : nums2) {
                    temp = i + j;
                    if (map.containsKey(temp)) {
                        map.put(temp, map.get(temp) + 1);
                    } else {
                        map.put(temp, 1);
                    }
                }
            }
            //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
            for (int i : nums3) {
                for (int j : nums4) {
                    temp = i + j;
                    if (map.containsKey(0 - temp)) {
                        res += map.get(0 - temp);
                    }
                }
            }
            return res;
        }
    }
}

LeetCode 15 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

思路：

本题的难点在于去重。三个元素更改顺序不算新的。使用双指针写法。首先需要对数组进行一个排序操作。方便使用双指针法移动

规定一个起始位置，起始位后后的最左最右规定left和right。判断三数之和的时候，起始位置不动，left和right由于是数组其他元素的

最大最小值，可以根据计算结果的偏差，调整left和right，最终寻找到一个合适的值。

本题的重点在于去重操作

a的去重（起始不变的那个元素）：

也就是不变的当前起始位置，需要与上一个循环的起始位置值比较是否相同，如果相同，没有移动的意义，需要把起始位置继续后移。num[i] == num[i-1]，continue跳过。 这样做防止取重复的固定位置的值。

为什么不用num[i] == num[i+1]?因为如果是【-1，-1，2，3，4】。我在取到第一个-1就去判断第二个位置的-1，这样做的话，就把[-1,-1,2]的这种可能排除掉了，如果取后一位进行比较，会影响到b的取值，不可取。

所以要和前一位比较最合理。

b和c的去重：

left和right的值，不能与移动路径的下一位相同，这个很好理解。如果right和left的下一个移动路径上的值相同，那么这次移动获取到的值是没有意义的。

代码：

package com.dwj.LeetCode.HashList;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 判断三数之和等于0的集合。
 */
public class ThreeNumberPlus {
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            Arrays.sort(nums);

            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > 0) {
                    return result;
                }

                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }

                int left = i + 1;
                int right = nums.length - 1;
                while (right > left) {
                    int sum = nums[i] + nums[left] + nums[right];
                    if (sum > 0) {
                        right--;
                    } else if (sum < 0) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        right--;
                        left++;
                    }
                }
            }
            return result;
        }
    }
}