三数之和

leetCode-15（三数之和）

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

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

示例 1：

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

示例 2：

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

示例 3：

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

解法一：排序+双指针+去重

  • 先对数组进行排序

  • 遍历排序的数组，固定第一个值，设置左右指针，

  • image-20220811105320802

  • 去重

代码为：

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        if (nums==null || nums.length<3) return res;
        //排序
        Arrays.sort(nums);
        //固定一个值
        for (int i = 0;i<n;i++){
            //固定的值，如果大于0，则直接continue
            if (nums[i]>0) continue;
            int l = i+1;
            int r = n-1;
            while (l<r){
                int sum = nums[i] + nums[l] + nums[r];
                if (sum==0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[l]);
                    list.add(nums[r]);
                    //去重
                    if (!res.contains(list)) res.add(list);
                    l++;
                    r--;
                }else if (sum<0){
                    l++;
                }else if (sum>0){
                    r--;
                }
            }
        }
        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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        if (nums==null || nums.length<3) return res;
        //排序
        Arrays.sort(nums);
        //固定一个值
        for (int i = 0;i<n;i++){
            //固定的值，如果大于0，则直接continue
            if (nums[i]>0) continue;
            //如果和前一个固定的值相等，则直接continue
            if (i>0 && nums[i]==nums[i-1]) continue;
            int l = i+1; //左指针
            int r = n-1;  //右指针
            while (l<r){
                int sum = nums[i] + nums[l] + nums[r];
                if (sum==0){
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));   //将数组转化为list集合
                    while (l+1<n && nums[l]==nums[l+1]) l++;  //如果和上一个指针的数相等，则跳过
                    while (r-1>=0 && nums[r]==nums[r-1]) r--;   //如果和上一个指针的数相等，则跳过
                    l++;
                    r--;
                }else if (sum<0){
                    l++;
                }else if (sum>0){
                    r--;
                }
            }
        }
        return res;
    }
}

两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

解法二：暴力

两个for循环

代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int res[] = new int[2];
        int n  = nums.length;
        for(int i = 0;i<n;i++){
            for(int j = i+1;j<n;j++){
                if (nums[i]+nums[j]==target){
                    res[0] = i;
                    res[1] = j;
                }
            }
        }
        return res;
    }
}

解法二：map

遍历数组，将数存储到map中，遍历中判断map是否有（target-该数），如果有则找到。直接返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int n = nums.length;
        int res[] = new int[2];
        for(int i = 0;i<n;i++){
            if(map.containsKey(target-nums[i])){
                res[0] = map.get(target-nums[i]);
                res[1] = i;
            }else{
                map.put(nums[i],i);
            }
        }
        return res;
    }
}

解法三：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        //这里要定义两个数组，因为如果进行排序后，原数据所对应的下标改变了，所以要定义二维数组存储坐标位置
        int a[][] = new int[n][2];  
        //将数据和坐标放入二维坐标中
        for (int i = 0;i<n;i++){
            a[i][0] = nums[i];
            a[i][1] = i;
        }
        //根据数据值进行排序
        Arrays.sort(a, (a1,b1) -> a1[0]-b1[0]);
        int l = 0;
        int r = n-1;
        int res[] = new int[2];
        while (a[l][0]+a[r][0]!=target){
            if (a[l][0]+a[r][0]<target) l++;
            else if (a[l][0]+a[r][0]>target) r--;
        }
        return new int[] {a[l][1], a[r][1]};  //返回原数据的位置
    }
}
算法 > leetCode > 中等题
三数之和
http://example.com/2022/08/11/三数之和/
作者
zlw
发布于
2022年8月11日
许可协议