Julia's BLOG

LeetCode-15 三数之和

2019-02-13

1. 题面

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

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

1
2
3
4
5
6
7
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

2. 解答

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) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        // 方法一 暴力枚举
        // for(int i = 0;i<nums.length-2;i++) {
        //     for(int j = i+1;j<nums.length-1;j++) {
        //         for(int k = j+1;k<nums.length;k++) {
        //             if(nums[i] + nums[j] + nums[k] == 0) {
        //                 if(!list.contains(Arrays.asList(nums[i],nums[j],nums[k])))
        //                     list.add(Arrays.asList(nums[i],nums[j],nums[k]));
        //             }
        //         }
        //     }
        // }
        
        // 方法二
        int i = 0;
        while(i<nums.length-2) {
            if(nums[i] > 0)
                break;
            int j = i+1;
            int k = nums.length-1;
            while(j<k) {
                int sum  = nums[i]+nums[j]+nums[k];
                if(sum == 0) list.add(Arrays.asList(nums[i],nums[j],nums[k]));
                if(sum <= 0) while(nums[j] == nums[++j] && j<k);
                if(sum >= 0) while(nums[k] == nums[--k] && j<k);
            }
            while(nums[i] == nums[++i] && i<nums.length-2);
        }
        return list;
    }
}
Tags: LeetCode
← LeetCode-14 最长公共前缀 LeetCode-20 有效的括号 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章