Leetcode 面试150题 15. 三数之和 中等

系列博客目录

好的，以下是整理后的题目描述、示例和问题细节，供你直接粘贴使用：

15. 三数之和 中等

题目描述：
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

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

输出： [[-1,-1,2],[-1,0,1]]

解释：

• nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
• nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
• nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0

不同的三元组是 [-1,0,1] 和 [-1,-1,2]。

注意：输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,-1]

输出： [[-1,0,1]]

解释：

• nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0

只有一个三元组 [-1, 0, 1]。

示例 3：

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

输出： [[0,0,0]]

解释：
唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

解答

一开始没有整体思路，但是想到了可以确定一个数字，然后变成两数之和问题。然后做了一个leetcode的两数之和的题目。其官方题解如下。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

然后针对两数之和扩展到三数之和，自己写的代码如下。
但是遇到比如由无数个0组成的数组，会导致超出内存限制(之前是有合理的三个数，就加到最后结果中，然后通过一个Hashset来去除重复的数组)，直到加上下面代码。

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        HashMap<Integer,Integer> map = new HashMap<>();
        List<List<Integer>> nestedList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],i);
        }
        int index_x , index_y = 0 ;
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            index_x = i;
            for (int i1 = i+1; i1 < nums.length; i1++) {
            	if (i1 > i+1 && nums[i1] == nums[i1 - 1]) { //注意 这里i1要大于i+1,比如x指向-1，y指向-1，时候，这个时候不能跳过，这是个 -1 -1 找个2 就可以作为答案
                    continue;
                }
                List<Integer> list = new ArrayList<>();
                index_y = i1;
                if(map.containsKey(-(nums[index_x]+nums[index_y])) && map.get(-(nums[index_x]+nums[index_y]))>index_y){
                    list.add(nums[index_x]);
                    list.add(nums[index_y]);
                    list.add(-(nums[index_x]+nums[index_y]));
                    nestedList.add(list);
                }
            }
        }
        Set<List<Integer>> set = new HashSet<>(nestedList);
        return new ArrayList<>(set);  // 将 Set 转回 List
    }
}

但是代码只打败了10%的人，很差。学习了官方题解的双指针后，好了很多。代码如下。思路就是思路就是先排序，然后定住first，把他的负值作为target，然后我们针对second和third进行操作。因为在排好序后，如果我们取third为可以取到的最大值，然后递减，如果third+second的值小于了target，那之后的遍历就没有用了，因为之后只会更小。注意通过continue来跳过可能导致重复结果的遍历过程。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> nestedList = new ArrayList<>();
        int target = 0;
        int third = 0;
        for (int first = 0; first < nums.length; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            third = nums.length -1;
            target = - nums[first];
            for (int second = first+1; second < nums.length; second++) {
                if (second > first+1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while(second < third && nums[second]+nums[third]>target) third--;
                if(second == third) break;
                if(nums[second] + nums[third] == target){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    nestedList.add(list);
                }
            }
        }
        return nestedList;  // 将 Set 转回 List
    }
}