LeetCode_双指针_中等_15.三数之和

╰+攻爆jí腚メ 2023-10-06 18:01 111阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个包含 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/3sum

## 2.思路 ##

（1）暴力穷举法  
其思想是使用三层 for 循环，穷举所有可能的情况，将符合题目条件的及结果保存到 res 中。由于该方法的时间复杂度较高，所以在 LeetCode 上提交时会显示超出时间限制的提示。此外值得注意的是在查找的过程中要去掉重复的三元组。

（2）排序 & 双指针法  
此题与[LeetCode\_哈希表\_简单\_1.两数之和][LeetCode_1.]这题中的扩展（2）类似，只不过元素个数变为 3。具体解题思路如下：

*  使用 for 循环来穷举第一个元素 nums\[i\]；
 *  对于每一个nums\[i\]，改写[LeetCode\_哈希表\_简单\_1.两数之和][LeetCode_1.]这题中扩展(2)的代码来找到和为 target - nums\[i\] 的二元组；
 *  如果能找到和为 targe - nums\[i\] 的二元组，那么该二元组再加上 nums\[i\] 便是和为 target 的三元组；
 *  使用 while 循环来跳过重复元素。

相关题目：  
[LeetCode\_双指针\_哈希表\_简单\_1.两数之和][LeetCode_1.]  
[LeetCode\_双指针\_中等\_16.最接近的三数之和][LeetCode_16.]  
[LeetCode\_双指针\_中等\_18.四数之和][LeetCode_18.]  
[LeetCode\_双指针\_中等\_167.两数之和 II - 输入有序数组][LeetCode_167._ II -]  
[LeetCode\_哈希表\_中等\_454.四数相加 II][LeetCode_454._ II]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
    	public List < List < Integer >> threeSum(int[] nums) {
        
    	    //对数组进行排序
    	    Arrays.sort(nums);
    	    //res用于存储结果
    	    List<List<Integer>> res = new ArrayList<>();
    	    for (int i = 0; i < nums.length - 2; i++) {
        
    	        //如果在数组排序后nums[i]为正数，则说明在nums[i]之后不存在符合题目条件的三元组
    	        if (nums[i] > 0) {
        
    	            break;
    	        }
    	        //如果当前相邻的三个元素之和大于0，则说明之后不存在符合题目条件的三元组
    	        if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
        
    	            break;
    	        }
    	        //如果当前相邻的三个元素之和小于0，直接进行下一趟循环
    	        if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] < 0) {
        
    	            continue;
    	        }
    	        //在排序后，若nums[i] == nums[i-1]便直接进行下一趟循环的目的是防止包含重复的三元组
    	        if (i > 0 && nums[i] == nums[i - 1]) {
        
    	            continue;
    	        }
    	        for (int j = i + 1; j < nums.length - 1; j++) {
        
    	            //剪枝操作，同上
    	            if (nums[i] + nums[j] + nums[j + 1] > 0) {
        
    	                break;
    	            }
    	            if (nums[i] + nums[j] + nums[nums.length - 1] < 0) {
        
    	                continue;
    	            }
    	            //去掉重复的三元组
    	            if (j > i + 1 && nums[j] == nums[j - 1]) {
        
    	                continue;
    	            }
    	            for (int k = j + 1; k < nums.length; k++) {
        
    	                //剪枝操作，同上
    	                if (nums[i] + nums[j] + nums[k] > 0) {
        
    	                    break;
    	                }
    	                if (nums[i] + nums[j] + nums[nums.length - 1] < 0) {
        
    	                    continue;
    	                }
    	                //去掉重复的三元组
    	                if (k > j + 1 && nums[k] == nums[k - 1]) {
        
    	                    continue;
    	                }
    	                if (nums[i] + nums[j] + nums[k] == 0) {
        
    	                    //将结果保存到res中
    	                    res.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
    	                }
    	            }
    	        }
    	    }
    	    return res;
    	}
    }

//思路2————排序 & 双指针法
    class Solution {
        
    	public List<List<Integer>> threeSum(int[] nums) {
        
    	    //目标和 target
    	    int target = 0;
    	    int length = nums.length;
    	    //对数组进行排序
    	    Arrays.sort(nums);
    	    // res 用于存储结果
    	    List<List<Integer>> res = new ArrayList<>();
    	    //遍历三元组的第一个数
    	    for (int i = 0; i < length; i++) {
        
    	        //计算有序数组 nums[satrt...nums.length - 1] 中所有和为 target - nums[i] 的元素对
    	        List<List<Integer>> tumples = twoSum(nums, i + 1, target - nums[i]);
    	        //如果找到和为 targe-nums[i] 的二元组，那么该二元组再加上 nums[i] 便是和为 target 的三元组
    	        for (List<Integer> tumple : tumples) {
        
    	            tumple.add(nums[i]);
    	            res.add(tumple);
    	        }
    	        //跳过重复元素
    	        while (i < length - 1 && nums[i] == nums[i + 1]) {
        
    	            i++;
    	        }
    	    }
    	    return res;
    	}
    	
    	/*
    	    (1) 计算有序数组 nums[satrt...nums.length - 1] 中所有和为 target 的元素对
    		(2) 改写自【LeetCode_双指针_哈希表_简单_1.两数之和】
    	*/
    	public List<List<Integer>> twoSum(int[] nums, int start, int target) {
        
            // res 用于存储结果
            List<List<Integer>> res = new ArrayList<>();
            //定义双指针
            int left = start, right = nums.length - 1;
            while (left < right) {
        
                int sum = nums[left] + nums[right];
                int leftVal = nums[left], rightVal = nums[right];
                if (sum == target) {
        
                    //将找到的元素对保存起来
                    res.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
                    //跳过所有重复的元素
                    while (left < right && nums[left] == leftVal) left++;
                    while (left < right && nums[right] == rightVal) right--;
                } else if (sum < target) {
        
                    //增大 sum 的值，即将 left 向右移动
                    while (left < right && nums[left] == leftVal) left++;
                } else {
        
                    //减小 sum 的值，即将 right 向左移动
                    while (left < right && nums[right] == rightVal) right--;
                }
            }
            return res;
        }
    }

[LeetCode_1.]: https://blog.csdn.net/weixin_43004044/article/details/118055101
[LeetCode_16.]: https://blog.csdn.net/weixin_43004044/article/details/118110152
[LeetCode_18.]: https://blog.csdn.net/weixin_43004044/article/details/118164049
[LeetCode_167._ II -]: https://blog.csdn.net/weixin_43004044/article/details/129296040
[LeetCode_454._ II]: https://blog.csdn.net/weixin_43004044/article/details/125439346