双指针解三数之和_给你一个包含n个整数的数组nums,判断nums中是否存在三个元素a, b,c,使得a+b +c =

1. 题目

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

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

示例1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例2：

输入：nums = []
输出：[]

示例3：

输入：nums = [0]
输出：[]

提示：

• 0<=nums.length<=3000

• -10^5 <= nums[i] <= 10^5

2. 解题思路

1. 排序
2. 定一移二，双指针

3. 代码实现

• java

import java.util.*;

public class Solution1 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 数组长度
        int[] nums = new int[n];

        // input
        for (int i = 0; i < n; i ++){
            nums[i] = sc.nextInt();
        }

        List<List<Integer>> res = threeSum(nums);

        for (int i = 0; i < res.size(); i ++){
            System.out.println(res.get(i));
        }
    }

    static List<List<Integer>> threeSum(int[] nums){

        List<List<Integer>> res = new ArrayList<>();

        // sort 排序
        Arrays.sort(nums);

        // 循环寻找
        for (int i = 0; i < nums.length - 2; i ++){

            // 如果nums[i]>0, break，因为之后的值的和不可能 < 0
            if (nums[i] > 0){
                break;
            }

            // 过滤重复掉的
            if (i > 0 && nums[i] == nums[i-1]){
                continue;
            }

            // 双指针：左右指针
            int left = i + 1;
            int right = nums.length - 1;

            // 寻找值：target
            int target = -nums[i];

            while(left < right){

                int sums = nums[left] + nums[right];
                if (sums == target){
                    // 找到一组，加入到集合中
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 过滤重复的
                    while (left < right && nums[left] == nums[left + 1]){
                        left ++;
                    }
                    while (left < right && nums[right] == nums[right - 1]){
                        right --;
                    }

                    left ++;
                    right --;

                } else if (sums < target) {
                    left ++;
                }else {
                    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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

4. 牵扯集合框架讲解

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

public class Solution1 {
    public static void main(String[] args) {
        /*
        * Arrays.sort()
        * ArrayList:  [ java.util.ArrayList; ]
        *   - 添加元素 add(value)
        *   - 访问元素 get(index)  [数组的索引值从0开始]
        *   - 修改元素 set(index, value)
        *   - 删除元素 remove(index)
        *   - 计算arraylist 中元素数量 size()
        *   - 迭代数组列表
        *       - for
        *       - for-each
        *   - 排序： [java.util.Collections;]
        *       - Collections.sort(ArrayName)
        *   - 返回元素对应的索引值 indexOf()
        *   - 判空 isEmpty()
        *   - 转换成数组 toArray()
        *   - 转换成字符串 toString()
        * 
        *   - 二维数组定义：
        *
        * Arrays.asList(value1, value2, ...)
        * */

        ArrayList<String> sites = new ArrayList<String>();

        sites.add("google");
        sites.add("runoob");
        sites.add("taobao");
        sites.add("weibo");

        System.out.println(sites);
        System.out.println(sites.get(2));

        // 修改元素
        sites.set(2, "yuan_web");
        System.out.println(sites.get(2));

        // for迭代数组列表元素
        for (int i = 0; i < sites.size(); i ++){
            System.out.println(sites.get(i));
        }

        // for_each迭代
        for (String i : sites){
            System.out.println(i);
        }

        Collections.sort(sites);

        for (String i : sites){
            System.out.println(i);
        }


        // 二维数组定义
        List<List<Integer>> res = new ArrayList<>();

        res.add(Arrays.asList(22, 33));
        res.add(Arrays.asList(2122, 12, 33));
        res.add(Arrays.asList(2222, 33));

        System.out.println(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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74

在基本知识都不会，需要别人帮助，打扰他人的时候（在别人忙的时候），那一刻会超级无助。
希望自己可以强大到支撑自己所有的野心，那种无助感，总会让自己瞬间崩溃。
脚踏实地、稳稳当当努力，加油。