三数之和

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

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

我刚看到这个题目的时候我想到的是之前做过一个题目两数之和等于特定值,现在a + b + c = 0 其实可以转换给 a + b = -c 这样问题,那么我遍历一遍数组,每次固定一个值nums[k], 问题就转换成在[k,i]的区间内寻找所有满足条件nums[lo] + nums[hi] = -nums[k]的问题了

 public List<List<Integer>> threeSum(int[] nums) {
        nums = Arrays.sort(nums);
        List<List<Integer>> result  = new ArrayList<>();
        for(int i = 0; i < nums.length - 2; i++) {
            int target = 0 - nums[i];
            //这个地方传的数组里面元素应该移动,每次传的数组需要变化
            //重复问题没解决
            List<List<Integer>> data = twoSum(nums, target);
            result.addAll(data);
        }
        return result;    
    }

    public List<List<Integer>> twoSum(int[] nums, int target){
       Map<Integer, Integer> map = new HashMap<>();
       List<List<Integer>> res = new ArrayList<>();
       for(int i = 0; i < nums.length; i++) {
           int key = target - nums[i];
           if(map.containsKey(key)) {
               res.add(Arrays.asList(nums[i], key, target));
           }
           map.put(nums[i], i);
       } 
       return res;
    }

emmm, 自己的思路感觉问题不大真正动手写代码的时候还是发现一些问题, 于是看了下大佬提供的思路, nice

//shpolsky大佬提供的思路,非常的巧妙
public List<List<Integer>> threeSum(int[] num) {
    //先排序
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    //处理相同元素的情况
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}
文章目录