尺取法：PIPI的目标Ⅲ-蒲公英云

尺取法：PIPI的目标Ⅲ

文章目录

尺取法：PIPI的目标Ⅲ
- - 问题：
  - 思路：
  - 代码：

问题：

在这里插入图片描述

思路：

首先对数组R进行排序，如果直接枚举a,b,c的话，时间复杂度为O(n^3)，肯定会超时，那么我们接下来考虑使用尺取法来解决此题。
我们只枚举a，然后令b=a+1，即b为a的下一位，c=n。枚举过程如下：
如果此时R[a]+R[b]+R[c]==0，那么满足要求，我们输出结果，然后令b++，c- -，之后继续进行和的判断。
如果此时R[a]+R[b]+R[c]<0，那么显然我们的值小了。由于我们枚举的是a，所以此时a不能动，那么只能动b或者c，而只有动b才能让它变大，所以让b++，之后继续进行和的判断。如果此时R\[a\]+R\[b\]+R\[c\]>0，那么显然我们的值大了。a不能动，那么只能动b或者c，而只有动c才能让它变小，所以让c- -，之后继续进行和的判断。
当b在c之后或b和c重叠时，则我们已经枚举完了当前a的所有情况，则a移到下一位，继续进行枚举判断过程

题目要求我们输出不重复的答案，因此我们将< a, b, c >定义为三元组TriGroup，用一个HashSet来进行去重。需要注意的是，我们必须重写TriGroup的equals方法，因为我们这里的逻辑是当三元组中a,b,c的值对应相等，则认为两个TriGroup是同一个，而默认的equals方法是通过==判断实现的。hashCode方法也要重写，因为HashSet的add方法，调用的实际上是其内置的HashMap的put方法，该方法是要使用到键的hash值的，而计算hash值就是用的hashCode方法，因此我们重写hashCode方法，使其返回a,b,c共同决定的hash值

代码：

import java.util.*;
public class Main {
    static int[] array = new int[1005];
    static Set<TriGroup> set = new HashSet<>();
    public static void main(String[] args) {
        int a, b, c, n, i, aIndex, bIndex, cIndex;
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            set.clear();
            n = scanner.nextInt();
            for (i = 0; i < n; i++) {
                array[i] = scanner.nextInt();
            }
            Arrays.sort(array, 0, n);
            for (i = 0; i < n - 2; i++) {
                aIndex = i;
                bIndex = i + 1;
                cIndex = n - 1;
                a = array[aIndex];
                b = array[bIndex];
                c = array[cIndex];
                while (bIndex < cIndex) {
                    if (a + b + c < 0) {
                        bIndex++;
                        b = array[bIndex];
                    }
                    if (a + b + c > 0) {
                        cIndex--;
                        c = array[cIndex];
                    }
                    if (a + b + c == 0 && cIndex > bIndex) {
                        TriGroup triGroup = new TriGroup(a, b, c);
                        if (!set.contains(triGroup)) {
                            set.add(triGroup);
                            System.out.println(a + " " + b + " " + c);
                        }
                        bIndex++;
                        b = array[bIndex];
                        cIndex--;
                        c = array[cIndex];
                    }
                }
            }
        }
    }
}
class TriGroup {
    public int a;
    public int b;
    public int c;
    public TriGroup(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TriGroup triGroup = (TriGroup) o;
        return a == triGroup.a && b == triGroup.b && c == triGroup.c;
    }
    @Override
    public int hashCode() {
        return Objects.hash(a, b, c);
    }
}