[数据结构与算法]【LeetCode每日练手】三数之和

15. 三数之和

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

示例 1：

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

输入：nums = []
输出：[]
示例 3：

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

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

解法1：暴力解法

今天第一次暴力写这道题目，感觉自己像小白

1. 数据排序可以直接用
2. [] 说明是一个数组，求数组的长度 nums.length
3. 数据添加元素 是add 方法
4. List.contains() 方法，
5. 排序可以优化一些吧

List调用contains(Object
obj)方法时,会遍历List中的每一个元素,然后再调用每个元素的equals()方法去跟contains()方法中的参数进行比较,如果有一个元素的equals()方法返回true则contains()方法返回true,否则所有equals()方法都不返回true,则ontains()方法则返回fals

e

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ans =new ArrayList();
     for(Integer i=0;i<nums.length;i++){
         for(Integer j=i+1;j<nums.length;j++){
             for(Integer k=j+1;k<nums.length;k++){
                  List<Integer> temp = new ArrayList();
                    temp.add(nums[i]);
                    temp.add(nums[j]);
                    temp.add(nums[k]);
                 if (nums[i]+nums[j]+nums[k]==0 && !ans.contains(temp)){
                    ans.add(temp);
                 }
             }
         }
     }   
     return ans;
    }
}

解法2：双指针+排序 解法

双指针还是有意思的，要特别注意处理边界条件

排序 + 双指针 本题的难点在于如何去除重复解。

算法流程： 特判，对于数组长度 nn，如果数组为 nullnull 或者数组长度小于 33，返回 [][]。 对数组进行排序。
遍历排序后数组： 若 nums[i]>0nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 00，直接返回结果。
对于重复元素：跳过，避免出现重复解 令左指针 L=i+1L=i+1，右指针 R=n-1R=n?1，当 L<RL<R 时，执行循环： 当
nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,RL,R 移到下一位置，寻找新的解 若和大于 00，说明 nums[R]nums[R] 太大，RR 左移 若和小于 00，说明
nums[L]nums[L] 太小，LL 右移 复杂度分析 时间复杂度：O\left(n^{2}\right)O(n 2 )，数组排序
O(N \log N)O(NlogN)，遍历数组 O\left(n\right)O(n)，双指针遍历
O\left(n\right)O(n)，总体 O(N \log
N)+O\left(n\right)*O\left(n\right)O(NlogN)+O(n)?O(n)，O\left(n^{2}\right)O(n
2 ) 空间复杂度：O(1)O(1)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans =new ArrayList();
        Arrays.sort(nums);
        if(nums==null || nums.length<3) return ans;
        Integer L=0;
        Integer R=0;
        for(Integer i=0;i<nums.length;i++){
            if(i>0 && nums[i-1]==nums[i]) continue;
            L=i+1;
            R=nums.length-1;
            while (L<R){
                if (nums[i]+nums[L]+nums[R]==0){
                    List<Integer> temp = new ArrayList();
                    temp.add(nums[i]);
                    temp.add(nums[L]);
                    temp.add(nums[R]);
                    ans.add(temp);
                    L=L+1;
                    R=R-1;
                }else if(nums[i]+nums[L]+nums[R]>0){
                    R=R-1;
                }else{
                    L=L+1;
                }
                while(R>L && R<nums.length-1 && nums[R+1]==nums[R]) R=R-1;
                while(R>L && L-1>i && nums[L-1]==nums[L]) L=L+1;
            }
        }
        return ans;
    }
}