三数之和 + 双指针 + 四数之和

77 阅读 0 评论 51 点赞

我是靠谱客的博主淡淡老师，最近开发中收集的这篇文章主要介绍三数之和 + 双指针 + 四数之和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

三数之和（https://leetcode-cn.com/problems/3sum/）
给你一个包含 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]
输出：[]

分析题意：
1.在一个整数数组中找出三个元素，使其和为0；
2.三个元素不能重复；

题意是似乎就是这么简单，我们第一想法就是循环，一直for，一直循环，这样的做的结果我先不说超不超时，能写出来的人就已经很牛逼了，所以这道题我们使用到了双指针法。

本题思路：

1.我们将数组nums进行从小到大排序;
2.定义一个左指针left，右指针right；
3.假设 a = nums[i]，b = nums[left] ， c = nums[right] ；
在这里插入图片描述
4.首先保持i指针不动，我们对a + b + c进行判断，如果a+b+c > 0,那说明right过大，我们要将right指针向左移动一个单位，因为我们已经将数组nums从小到大排序；

5.如果a+b+c < 0,那说明left过小，left向右一个单位；
在这里插入图片描述
6.如果a+b+c=0，那就将其存储起来；

大题思路就是这样，但这其中有很多细节要处理，说是说不清楚的，我们拿代码来看，我会在代码中对一些细节处理进行注释。

java代码：

class Solution {
     public List<List<Integer>> threeSum(int[] nums) {
     	//定义一个ArrayList存储ArrayList(如果不懂，先看下面代码自然会懂）
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        //快排
        Arrays.sort(nums);
        int n = nums.length; 
        //左指针
        int left = 1;
        //右指针
        int right = n - 1;
        int sum = 0;
        for (int i = 0 ; i < n ; i++) {
            //如果数组第一个值就大于0，说明不存在题意要求情况，直接返回
            if (nums[i] > 0) {
                return list;
            } 
            //去重，i等于0的时候不进行去重，只有当i > 1时才判断i是否和i-1相等
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            //如果i指针移动一个单位，那么left也要移动一个单位，因为不能重复
            left = i + 1;
            right = n - 1;
            //当左指针大于大于右指针的时候跳出循环
            
            while (left < right) {
                sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                	//创建一个ArrayList来存储三元组
                    List<Integer> sumList = new ArrayList<Integer>();
                    sumList.add(nums[i]);
                    sumList.add(nums[left]);
                    sumList.add(nums[right]);
                    //将三元组存储在list里面
                    list.add(sumList);
                    //去重，和i的去重一个道理
                    while(left < right && nums[right - 1] == nums[right]) right--;
                    while(left < right && nums[left + 1] == nums[left]) left++; 
                    //每次找到答案两指针同时收缩
                    left++;
                    right--;
                }
                else if (sum > 0) {
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return list;
    }
}

可能有同学不明白left和right的去重，我在这里解释一下：
在这里插入图片描述
比如说我们找到[-1,1,2]这个符合条件的三元组（上图），我们把上图的第4个索引变成2，方便我们解释（下图），那么我们进行去重处理；

当我们判断nums[right - 1] == nums[right] 时，right–，那么就会变成这样
在这里插入图片描述
就相当于这是一样的结果，直接跳过了，left道理和right一样，然后再进行right–和left++；
我在这里只是举个例子，让大家明白为什么那么写。