LeetCode百题【三数之和】

题目描述

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

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

示例 1：

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

示例 2：

1 2	`输入：nums = [] 输出：[]`

示例 3：

1 2	`输入：nums = [0] 输出：[]`

提示：

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

解法

排序+双指针
- 先对数组进行排序，这样可以使重复的元素排在一起方便去重
- 对a进行遍历，剩下的数（b+c）进行遍历找结果就是两数之和
- 注意内存优化

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();
        //不满足3个数直接返回
        if (nums.length<=2){
            return ans;
        }
        //排序 从小到大
        Arrays.sort(nums);
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            //排序过后去重
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            //相当于找到了a，剩下的数就是两数之和
            twoSum(ans, nums, nums[i],i+1, n-1);
        }
        return ans;
    }

    /**
     * 两数之和
     * @param ans   存储最后的结果
     * @param nums  数组
     * @param a     数a
     * @param left  数b的下标 左指针
     * @param right 数c的下标 右指针
     */
    public void twoSum(List<List<Integer>> ans,int[] nums,int a,int left,int right){
        while (left<right){
            int sum=nums[left]+nums[right];
            if (sum==-a){
                //直接再new一个list会导致超内存,这里使用aslist方法
                ans.add(Arrays.asList(a,nums[left],nums[right]));
                //还有两个while循环十分耗内存这两处优化其一即可
                while (left<right && nums[left] == nums[left+1]) left++; // 去重
                while (left<right && nums[right] == nums[right-1]) right--; // 去重
                left++;
                right--;
            }
            else if (sum<-a){
                left++;
            }else {
                right--;
            }
        }
    }
}