LeetCode_15&16_三数问题

1.题目描述

(1) 三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

(2)最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

2.思路分析

1.在一个数组中找一个数：搜索，二分查找（时间复杂度O(N)）
2.在一个数组中找两个数：LeetCode_01两数之和问题，LeetCode_11盛最多水的容器（时间复杂度O(N)）
两种思路：
①用HashMap或者HashSet来存储已经遍历的，空间换时间
②双指针，通过移动两个指针来遍历
3.在一个数组中找三个数：LeetCode_15三数之和，LeetCode_16最接近的三数之和
通常的处理步骤：
（1）将当前数组排序，时间复杂度O(NlogN)
（2）选一个固定值，再双指针遍历。时间复杂度O(N^2)

本题的详细思路
①首先进行数组排序，Arrays.sort()
②在数组 nums 中，进行遍历，每遍历一个值利用其下标i，形成一个固定值 nums[i]
③再使用前指针指向 start = i + 1 处，后指针指向 end = nums.length - 1 处，也就是结尾处
④根据 sum = nums[i] + nums[start] + nums[end] 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 ans
⑤同时判断 sum 与 target 的大小关系，因为数组有序，如果 sum > target 则 end--，如果 sum < target 则 start++，如果 sum == target 则说明距离为 0 直接返回结果

3.代码实现

三数之和：

package part2;

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

/**
 * @author haiboWu
 * @create 2020-02-03 10:44
 */
public class No_15 {
    public static void main(String[] args) {
        int nums[] = {-4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0};
        System.out.println(threeSum(nums));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        int len = nums.length;
        if (nums == null || len < 3) return lists;
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[i] > 0) break;
            int l = i + 1, r = len - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[l]);
                    list.add(nums[r]);
                    lists.add(list);
                    l++;
                    r--;
                } else if (sum > 0) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        return lists;
    }
}

最接近的三数之和

package part2;

import java.util.Arrays;

/**
 * @author haiboWu
 * @create 2020-02-03 17:13
 */
public class No_16 {
    public static void main(String[] args) {
        int nums[] = {-1, 2, 1, -4};
        System.out.println(threeSumClosest(nums, 1));

    }

    public static int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        int sum = nums[0] + nums[1] + nums[2];
        int ans = sum;
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            int l = i + 1, r = len - 1;
            while (l < r) {
                sum = nums[i] + nums[l] + nums[r];
                if(Math.abs(ans-target)>Math.abs(sum-target)){
                    ans=sum;
                }
                if (sum == target) return target;
                if (sum > target) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        return ans;
    }
}