Leetcode15

Manan
Page content

题目描述

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

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

题目链接：https://leetcode-cn.com/problems/3sum/

思路阐述

显然此题可以通过暴力求解的方式，使用三个循环依次遍历数组求解。

暴力的方式不是最优的方式，更为简单直观的方式是：排序 + 三指针。

题目给出的数组是无序的，无序数组的可操作性比较低，因为元素的随机排列使得算法求解失去目的性。在求解之前需要对无序的数组进行排序，然后采用固定一个指针，剩下的两个指针需要根据当前的结果选择贪心的策略进行移动。

首先最外层循环变量front是我们需要固定下来的指针。一旦front固定下来，只需考虑front之后的子序列。

在子序列中，一个指针定义为mid位于子序列的最开头，另一个指针定义为rear位于子序列的最末尾。mid指针需要位于rear指针的左侧。因为整个序列有序，所以子序列也有序（假设序列递增）

所以由当前三个指针front, mid和rear便可以确定序列中的三个数的组合。

  1. $ nums[front] + nums[mid] + nums[rear] == 0 $
  2. $ nums[front] + nums[mid] + nums[rear] < 0 $
  3. $ nums[front] + nums[mid] + nums[rear] > 0 $

case 1: 符合题目要求的情况 case 2: 需要将mid指针向后移动（序列递增）找到一个更大的数。 case 3: 需要将rear指针向前移（序列递增）找一个更小的数。

题目要求，不可以出现重复的元组组合，所以需要进行去重操作。

去重的思想就是，任意一个指针移动到下一个位置的时候，如果和上一位置的元素相等，那么直接跳过这个位置。

Java AC代码

var res = new ArrayList<List<Integer>>();
if (nums.length < 3) return res;
// 对数组进行排序
Arrays.sort(nums);
if (nums[0] > 0) return res;
boolean b = Arrays.stream(nums).allMatch(it -> it == 0);
if (b){
    res.add(List.of(0, 0, 0));
    return res;
}
for (int front = 0; front < nums.length; ++front) {
    // 去重操作
    if (front > 0 && nums[front] == nums[front - 1]) continue;
    var mid = front + 1;
    var rear = nums.length - 1;
    while (mid < rear) {
        var sum = nums[front] + nums[rear] + nums[mid];
        if (sum > 0)  {
                rear --;
        } else if (sum < 0) {
            mid++;
        } else {
            res.add(List.of(nums[front], nums[mid], nums[rear]));
            while (mid < rear && nums[mid] == nums[mid + 1]) mid++; // 去重操作
            while (mid < rear && nums[rear] == nums[rear- 1]) rear--; // 去重操作
            mid++; rear--;
        }
    }
}