three-sum（3个数的和）_three sum

题目1：

给定一个n个整数的数组S，是否存在S中的元素a，b，c，使得a + b + c = 0？ 查找数组中所有唯一的三元组，它们的总和为零。
注意：
三元组中的元素（a，b，c）必须是非降序。 （即，a≤b≤c）
解决方案集不能包含重复的三元组。

例如，给定数组S = {-1 0 1 2 -1 -4}，
     解决方案集是：
     （-1,0,1）
     （-1，-1,2）

解题思路：

（1）首先对数组进行排序（从小到大）
（2）依次取出第 i 个数（i从0开始），并且不重复的选取（跳过重复的数）
（3）这样问题就转换为 2 个数求和的问题（可以用双指针解决方法）2 数求和问题
（4）定义两个指针：左指针（left） 和 右指针（right）
（5）找出固定 left， 此时left所指的位置为数组中最小数，再找到两个数和 不大于 target 的最大 right 的位置
（6）调整 left 的位置（后移），求解和是否为 target O(n)
（7）时间复杂度：O(nlogn) + O(n)

代码实现：

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

public class Solution {
    public static void main(String[] args) {
        int[] num = {-2, 0, 1, 1, 2};
        System.out.println(new Solution().threeSum(num));
    }

    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        if (num == null) {
            return result;
        }
        //排序
        Arrays.sort(num);
        int sum, left, right;

        for (int i = 0; i < num.length - 2; i++) {
            //避免重复, 比如前面计算了以-1开头,后面就不用计算了
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            left = i + 1;
            right = num.length - 1;
            /**
             * 固定一个数,从后面的数中选出两个数,因为数组是有序的,所以可以
             * 用两个数组下标left和right,left指向当前元素的后一个位置,right指向最后一个位置
             * 三个数相加的和等于0时,加入解集;
             * 小于0时,把left往右边移动;
             * 大于0时,把right往左边移动;
             */
            while (left < right) {
                sum = num[left] + num[right];
                if (sum + num[i] == 0) {
                    ArrayList<Integer> solution = new ArrayList<>();
                    solution.add(num[i]);
                    solution.add(num[left]);
                    solution.add(num[right]);
                    result.add(solution);
                    left++;
                    right--;
                    //这个优化必须加,不加时间超限,其实这个优化也没太大作用嘛
                    while (left < right && num[left] == num[left - 1]) {
                        left++;
                    }
                    while (left < right && num[right] == num[right + 1]) {
                        right--;
                    }
                } else if (sum + num[i] < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

题目2：

给定一个n个整数的数组S，在S中找到三个整数，使得总和最接近给定的数字，target。 返回三个整数的总和。 你可以假设每个输入都只有一个解决方案。
例如，给定数组S = {-1 2 1 -4}，并且target = 1。
     最接近target的总和是2.（-1 + 2 + 1 = 2）。

解题思路：

解题思路与题目1相同

代码实现：

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public int threeSumClosest(int[] num, int target) {
        int dv = Integer.MAX_VALUE;//数组中3数之和与target的差值
        int res = Integer.MAX_VALUE;//返回值
        Arrays.sort(num);
        for(int i = 0;i < num.length-2;i++){
            if(i != 0 && num[i] == num[i-1]){
                i++;
            }
            int left = i+1;
            int right = num.length-1;
            while(left < right){
                int sum = num[left]+num[right];
                if(sum+num[i] == target){
                    return target;
                }else if(sum+num[i] < target){
                    if(dv > Math.abs(sum+num[i]-target)){
                        dv = Math.abs(sum+num[i]-target);
                        res = sum+num[i];
                    }
                    left ++;
                }else{
                    if(dv > Math.abs(sum+num[i]-target)){
                        dv = Math.abs(sum+num[i]-target);
                        res = sum+num[i];
                    }
                    right --;
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

题目1来自牛客网leetcode
题目2来自牛客网leetcode