中等-18-四数之和

该文逐次讲述二数之和，三数之和，四数之和。

一，二数之和 LeetCode01

作为力扣第一题，应该很是经典了。回头翻两个月前做的解法，是暴力解法，当时还没学习哈希表，现在做个补充吧。

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

形象地说，暴力法是往后寻找匹配值，哈希表是往前寻找匹配值。

此题如果用双指针解法，对数组排序会打乱索引顺序，因此需要另外开辟一个数组。

public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int curTarget = target - nums[i];
            if (map.containsKey(curTarget))
                return new int[] { map.get(curTarget), i };
            map.put(nums[i], i);
        }
        return new int[]{};
    }

二，三数之和 LeetCode15

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

由二数之和可以考虑双指针解法，对每个元素，在剩余数组中找两数之和。双指针解法难点在于去重。

时间复杂度分析：排序：nlogn，迭代：n，双指针：n　　总复杂度：O(n²)

public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3)
            return new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length && nums[i] <= 0; i++) {
            if(i>0 && nums[i] == nums[i-1])　　//去重
                continue;
            int left = i + 1;
            int right = nums.length - 1;
            int target = 0 - nums[i];
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    while (left < right && nums[left] == nums[left + 1])　　//去重
                        left++;
                    while (left < right && nums[right] == nums[right - 1])　　//去重
                        right--;
                    left++;
                    right--;
                }
                else if (nums[left] + nums[right] < target)
                    left++;
                else if (nums[left] + nums[right] > target)
                    right--;
            }
        }
        return res;
    }

 三，四数之和 LeetCode18

仍然可以用双指针，在三数之和的基础上再嵌套一层遍历。

该题的哈希表解法下次回顾时在做补充。

public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums.length < 4)
            return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                int left = j + 1;
                int right = nums.length - 1;
                int curTarget = target - nums[i] - nums[j];
                while (left < right) {
                    if (nums[left] + nums[right] == curTarget) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        res.add(list);
                        while (left < right && nums[left] == nums[left + 1])
                            left++;
                        while (left < right && nums[right] == nums[right - 1])
                            right--;
                        left++;
                        right--;
                    } else if (nums[left] + nums[right] > curTarget)
                        right--;
                    else if (nums[left] + nums[right] < curTarget)
                        left++;
                }
            }
        }
        return res;
    }