乐趣区

关于leetcode:leetcode-15-3Sum-三数之和中等

一、题目粗心

给你一个整数数组 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]

输入:[]

解释:惟一可能的三元组和不为 0。

示例 3:

输出:nums = [0,0,0]

输入:[[0,0,0]]

解释:惟一可能的三元组和为 0。

提醒:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

起源:力扣(LeetCode)
链接:https://leetcode.cn/problems/…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。

二、解题思路

思路 1: 暴力求解,3 层循环,工夫复杂度为 O(N^3)

思路 2:3 层循环的加强版,a+b+c=0, 即 c =-(a+b),定义一个 map 省掉最初一个循环,二层循环,工夫复杂度为 O(N^2)

思路 3:sortfind,整个数组排序 O(NlogN),以示例 1 为例,先排序为 [-4, -1, -1, 0, 1, 2],定义一个 a 遍历,再遍历求 b,c,此时令 b 等于 a 接下来的第一个元素,c 为最初一个元素,判断 a +b+c<0 气节 b +1,如果 a +b+c>0 气节 c -1.

三、解题办法

3.1 Java 实现

public class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {if (i > 0 && nums[i] == nums[i-1]) {continue;}
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {int sum = nums[i] + nums[j] + nums[k];
                if (sum < 0) {j++;} else if (sum > 0) {k--;} else if (sum == 0) {ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
                    while (j < k && nums[j] == nums[j + 1]) {j++;}
                    while (j < k && nums[k] == nums[k - 1]) {k--;}
                    j++;
                    k--;
                }
            }
        }
        return ans;
    }
}

四、总结小记

  • 2022/10/23 马上就到程序员节日啦
退出移动版